In an adjacency list representation of an undirected simple graph \(G =…

PYQ GATE 2016

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: [vv] in the adjacency list of uu, and [uu] 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 |EE| = mm and |VV| = nn, 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?

  1. A.

    Θ(n2)Θ(n^2)

  2. B.

    Θ(n+m)Θ(n+m)

  3. C.

    Θ(m2)Θ(m^2)

  4. D.

    Θ(n4)Θ(n^4)

Attempted by 558 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…