Skip to content
GATETECH
Official PYQ · 2016Set 2 · Q41Graph Traversals (BFS, DFS)MCQ1 mark

GATE CS 2016 Set 2 Q41 — Graph Traversals (BFS, DFS)

Explain with AI

In an adjacency list representation of an undirected simple graph G=(V,E)G=(V, E), each edge (u,v)(u, v) has two adjacency list entries: [v][v] in the adjacency list of uu, and [u][u] in the adjacency list of vv. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If ∣E∣=m|E|=m and ∣V∣=n|V|=n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

Choose one option
View worked solution

Answer: B

To set the twin pointers efficiently, we need to pair each entry [v][v] in uu's adjacency list with its twin entry [u][u] in vv's adjacency list. There are 2m2m such entries in total across all adjacency lists.

We can achieve this in Θ(n+m)\Theta(n + m) time using the following algorithm:

  1. Create Tuples: For every vertex u∈Vu \in V and each neighbor vv in uu's adjacency list, create a tuple: (min⁡(u,v),max⁡(u,v),address of this entry)\left(\min(u, v), \max(u, v), \text{address of this entry}\right) There are exactly 2m2m such tuples.
  2. Sort the Tuples: Sort these 2m2m tuples using Radix Sort (with two passes of Counting Sort, since the vertex indices are in the range [1,n][1, n]). The time complexity of this sorting is Θ(n+m)\Theta(n + m).
  3. Link Twins: After sorting, the two twin entries corresponding to any edge (u,v)(u, v) will end up adjacent to each other in the sorted array. We can traverse the sorted array in a single pass of Θ(m)\Theta(m) steps and set the twin pointers of each adjacent pair to point to each other.

The overall time complexity is Θ(n+m)+Θ(m)=Θ(n+m)\Theta(n + m) + \Theta(m) = \Theta(n + m).

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Graph Traversals (BFS, DFS) questions