Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Go - 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 work grows when we explore these connections.

How does the number of points and connections affect the time to process a graph?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Visit all vertices and edges in a graph
func TraverseGraph(adjList map[int][]int) {
    for vertex := range adjList {
        // Process each vertex
        for _, neighbor := range adjList[vertex] {
            // Process each edge
            _ = neighbor
        }
    }
}
    

This code visits every vertex and then every edge connected to that vertex in an adjacency list graph.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over all vertices and their edges.
• How many times: Outer loop runs once per vertex (V times), inner loop runs once per edge connected to that vertex.

How Execution Grows With Input

As the number of vertices (V) and edges (E) grow, the total work grows roughly with both.

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

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

Final Time Complexity

Time Complexity: O(V + E)

This means the time to process the graph grows in direct proportion to 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 must visit each point and all its connections to fully explore the graph.

Interview Connect

Understanding how graph size affects processing time helps you explain your approach clearly and shows you know what matters when working with graphs.

Self-Check

"What if the graph was represented as an adjacency matrix instead of a list? How would the time complexity change?"

Practice

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

easy

A. Paths

B. Edges

C. Weights

D. Vertices

Solution

1. Step 1: Understand graph components

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

2. Step 2: Identify the term for nodes

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option D

4. Quick Check:

   Nodes = Vertices [OK]

Hint: Remember: nodes = vertices, connections = edges [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare an undirected graph using adjacency list in Go?

easy

A. graph := make(map[int][]int)

B. graph := make([][]int, 0)

C. graph := make(map[int]int)

D. graph := make([]int, 0)

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list uses a map from a vertex to a list of connected vertices.

2. Step 2: Choose correct Go syntax

   Using map[int][]int creates a map from int to slice of ints, perfect for adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Map of int to slice[int] = adjacency list [OK]

Hint: Adjacency list = map from node to list of nodes [OK]

Common Mistakes:

• Using map[int]int which stores single int, not list
• Using slice of slices without map for keys
• Using slice of ints which can't map nodes

3. What will be the output of the following Go code snippet representing a weighted directed graph adjacency list?

graph := map[int]map[int]int{
  1: {2: 5, 3: 10},
  2: {3: 2},
  3: {},
}
fmt.Println(graph[1][3])

medium

A. 2

B. 5

C. 10

D. 0

Solution

1. Step 1: Understand graph structure

   graph[1] is a map with keys 2 and 3, values 5 and 10 respectively.

2. Step 2: Access graph[1][3]

   graph[1][3] accesses the weight from vertex 1 to 3, which is 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Weight from 1 to 3 = 10 [OK]

Hint: Access nested map keys for weights: graph[from][to] [OK]

Common Mistakes:

• Confusing weight 5 (edge 1->2) with 1->3
• Assuming 0 means no edge but 3 has empty map
• Mixing up keys and values in nested maps

4. Identify the error in this Go code snippet for adding an edge to an undirected graph adjacency list:

func addEdge(graph map[int][]int, u, v int) {
  graph[u] = append(graph[u], v)
  graph[v] = append(graph[u], v)
}

medium

A. Appending v to graph[u] twice

B. Appending v to graph[v] incorrectly

C. Missing initialization of graph map

D. Using wrong data type for graph

Solution

1. Step 1: Analyze append statements

   First append adds v to graph[u], correct for edge u->v.

2. Step 2: Check second append

   Second append incorrectly appends v to graph[u] again instead of graph[v].

3. Final Answer:

   Appending v to graph[v] incorrectly -> Option B

4. Quick Check:

   Second append should be graph[v] = append(graph[v], u) [OK]

Hint: For undirected, append u to v's list and v to u's list [OK]

Common Mistakes:

• Appending to wrong slice variable
• Forgetting to append both directions
• Not initializing map slices before append

5. Given a weighted undirected graph represented as a map[int]map[int]int in Go, how can you ensure that adding an edge between two vertices u and v with weight w updates both directions correctly?

hard

A. graph[u][v] = w; graph[v][u] = w

B. graph[u][v] = w only

C. graph[v][u] = w only

D. graph[u][v] = w; graph[u][v] = w

Solution

1. Step 1: Understand undirected graph edge representation

   In undirected graphs, edges go both ways, so weights must be stored both ways.

2. Step 2: Update both directions in map

   Assign weight w to graph[u][v] and graph[v][u] to reflect undirected edge.

3. Final Answer:

   graph[u][v] = w; graph[v][u] = w -> Option A

4. Quick Check:

   Both directions updated = undirected edge [OK]

Hint: Update both graph[u][v] and graph[v][u] for undirected edges [OK]

Common Mistakes:

• Updating only one direction
• Assigning weight twice to same direction
• Confusing directed and undirected edge updates