###### UML

October 12, 2023###### Software-Engineering

October 12, 2023# Data-Structures

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 level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.

Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.

Visit every vertex level-wise 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 level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.

Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.

Visit every vertex level-wise 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