UML
October 12, 2023SoftwareEngineering
October 12, 2023DataStructures
Question 35

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 efﬁcient algorithm to set the twin pointer in each entry in each adjacency list?
Θ(n^{2})


Θ(n+m)


Θ(m^{2})


Θ(n^{4})

Question 35 Explanation:
Applying BFS on Undirected graph give you twin pointer.
Visit every vertex levelwise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.
Visit every vertex levelwise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.
Correct Answer: B
Question 35 Explanation:
Applying BFS on Undirected graph give you twin pointer.
Visit every vertex levelwise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.
Visit every vertex levelwise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.
Subscribe
Login
0 Comments