In an adjacency list representation of an undirected simple graph \(G =…
GATE · 2016 · CS · Set 2 · Computer Science & IT
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 428 students.
Show answer
Correct answer: B
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2