In an adjacency list representation of an undirected simple graph \(G =…
2016
In an adjacency list representation of an undirected simple graph \(G = (V,E)\), each edge \((u, v)\) has two adjacency list entries: [\(v\)] in the adjacency list of \(u\), and [\(u\)] in the adjacency list of \(v\). These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |\(E\)| = \(m\) and |\(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?
- A.
\(Θ(n^2)\) - B.
\(Θ(n+m)\) - C.
\(Θ(m^2)\) - D.
\(Θ(n^4)\)
Attempted by 208 students.
Show answer & explanation
Correct answer: B
Key idea: pair up the two adjacency-list entries of each undirected edge using a hash table keyed by the unordered endpoint pair.
Traverse every adjacency-list entry once (there are 2m entries total). For an entry that represents edge (u,v) compute the key (min(u,v), max(u,v)).
Use a hash table mapping the unordered edge key to the first-seen adjacency-entry pointer. When you encounter the other adjacency entry for the same edge, fetch the stored pointer and set the twin pointer in both entries, then remove the key.
Because each adjacency entry is inserted/looked-up exactly once and each hash operation is expected O(1), total time is Θ(n+m) (we also pay O(n) to initialize any per-vertex structures).
Why this is correct: in a simple undirected graph each edge appears in exactly two adjacency lists, so the algorithm pairs those two entries precisely once. Memory usage is higher due to the hash table, but the problem statement allows that.
A video solution is available for this question — log in and enroll to watch it.