Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Python - Time & Space Complexity

Time Complexity: Graph Terminology Vertices Edges Directed Undirected Weighted

O(V + E)

Understanding Time Complexity

Graphs are made of points and connections. We want to understand how the time to work with these grows as the graph gets bigger.

How does the number of points and connections affect the work needed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Simple graph representation using adjacency list
graph = {
    'A': [('B', 3), ('C', 5)],  # edges with weights
    'B': [('C', 2)],
    'C': [('A', 4)]
}

# Print all edges
for vertex in graph:
    for neighbor, weight in graph[vertex]:
        print(f"{vertex} -> {neighbor} with weight {weight}")

This code prints all connections (edges) from each point (vertex) in a weighted directed graph.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over vertices and their edges.
• How many times: Outer loop runs once per vertex (V times), inner loop runs once per edge from that vertex (sum of edges E).

How Execution Grows With Input

As the graph grows, the work grows with the number of vertices and edges.

Input Size (V, E)	Approx. Operations
V=10, E=15	~25 (10 + 15)
V=100, E=200	~300 (100 + 200)
V=1000, E=5000	~6000 (1000 + 5000)

Pattern observation: The work grows roughly with the sum of vertices and edges.

Final Time Complexity

Time Complexity: O(V + E)

This means the time to process the graph grows linearly with the number of points plus the number of connections.

Common Mistake

[X] Wrong: "The time depends only on the number of vertices or only on the number of edges."

[OK] Correct: Both vertices and edges matter because you visit each vertex and all its edges to process the graph fully.

Interview Connect

Understanding how graph size affects work helps you explain and write efficient graph algorithms confidently in interviews.

Self-Check

"What if the graph was undirected instead of directed? How would the time complexity change?"

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Vertices

B. Edges

C. Weights

D. Paths

Solution

1. Step 1: Understand graph components

   A graph consists of points called vertices and connections called edges.

2. Step 2: Identify the term for points

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option A

4. Quick Check:

   Points in graph = Vertices [OK]

Hint: Vertices are the points, edges are the lines connecting them [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are points
• Mixing paths with vertices

2. Which of the following is the correct way to represent a weighted edge from vertex A to vertex B with weight 5 in Python using a tuple?

easy

A. (5, A, B)

B. [A, B, 5]

C. {'A': 'B', 'weight': 5}

D. (A, B, 5)

Solution

1. Step 1: Understand tuple representation

   A weighted edge is often represented as a tuple (start_vertex, end_vertex, weight).

2. Step 2: Match the correct tuple format

   The tuple (A, B, 5) correctly shows an edge from A to B with weight 5.

3. Final Answer:

   (A, B, 5) -> Option D

4. Quick Check:

   Weighted edge tuple = (start, end, weight) [OK]

Hint: Weighted edges use (start, end, weight) tuple format [OK]

Common Mistakes:

• Using list instead of tuple
• Putting weight first
• Using dictionary instead of tuple

3. What will be the output of the following Python code snippet?

graph = { 'A': ['B', 'C'], 'B': ['C'], 'C': ['A'] }
print(len(graph['A']))

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Analyze the graph dictionary

   Key 'A' has a list of neighbors ['B', 'C'], so graph['A'] is ['B', 'C'].

2. Step 2: Calculate length of neighbors list

   len(graph['A']) counts the number of neighbors, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Neighbors of A = 2 [OK]

Hint: Count neighbors in adjacency list for vertex [OK]

Common Mistakes:

• Counting total keys instead of neighbors
• Confusing keys with values
• Off-by-one counting errors

4. Identify the error in the following Python code that tries to create an undirected graph using adjacency lists:

graph = { 'A': ['B'], 'B': ['C'], 'C': [] }
graph['C'].append('A')

medium

A. The code is correct for undirected graph

B. Appending 'A' to 'C' creates a cycle

C. The graph is directed, not undirected

D. Missing edge from 'B' to 'A'

Solution

1. Step 1: Understand undirected graph representation

   In an undirected graph, edges go both ways, so adjacency lists must be symmetric.

2. Step 2: Check the adjacency lists

   Initially, 'A' connects to 'B', but 'B' does not connect back to 'A', so it's directed.

3. Final Answer:

   The graph is directed, not undirected -> Option C

4. Quick Check:

   Undirected graph needs two-way edges [OK]

Hint: Undirected graphs have symmetric edges in adjacency lists [OK]

Common Mistakes:

• Assuming one-way edges are undirected
• Ignoring symmetry in adjacency lists
• Confusing cycles with direction

5. You have a weighted undirected graph represented as an adjacency list:

graph = {
  'A': [('B', 3), ('C', 5)],
  'B': [('A', 3), ('C', 1)],
  'C': [('A', 5), ('B', 1)]
}

What is the total weight of all edges in this graph?

hard

A. 18

B. 9

C. 6

D. 3

Solution

1. Step 1: List all edges with weights

   Edges: A-B(3), A-C(5), B-C(1). Each edge appears twice because graph is undirected.

2. Step 2: Sum weights and divide by 2

   Total sum counting duplicates = 3+5+3+1+5+1 = 18. Divide by 2 to avoid double counting: 18 / 2 = 9.

3. Final Answer:

   9 -> Option B

4. Quick Check:

   Sum weights once for undirected edges [OK]

Hint: Sum all weights then halve for undirected graphs [OK]

Common Mistakes:

• Counting edges twice
• Forgetting to divide by 2
• Ignoring weights in tuples