Graphs and Traversals Questions and Answers

Q: Let \(G\) be a directed graph and \(T\) a depth first search (DFS) spanning tree in \(G\) that is rooted at a vertex \(v\). Suppose \(T\) is also a breadth first search (BFS) tree in \(G\), rooted at \(v\). Which of the following statements is/are TRUE for every such graph \(G\) and tree \(T\) ?

The statement that always holds is There are no forward-edges in \(G\) with respect to the tree \(T\).A forward edge goes from a vertex u to a descendant w of u that is not its child, so w is at least two levels below u in T. In a BFS tree, every edge (u, w) satisfies depth(w) \(\le\) depth(u) + 1, because BFS reaches w no later than one step after u. Since T is a BFS tree, such an edge is impossible.The other statements can fail. A back edge, such as an edge from a child back to v, is allowed. A cross edge is possible too: with edges v\(\to\)a, v\(\to\)b and b\(\to\)a, the tree {v\(\to\)a, v\(\to\)b} is both a DFS and a BFS tree, and b\(\to\)a is a cross edge. Those examples also show G can have edges outside T.

Q: Let \(G(V, E)\) be an undirected and unweighted graph with 100 vertices. Let \(d(u, v)\) denote the number of edges in a shortest path between vertices \(u\) and \(v\) in \(V\). Let the maximum value of \(d(u, v)\), \(u, v \in V\) such that \(u \ne v\), be 30. Let \(T\) be any breadth-first-search tree of \(G\). Which ONE of the given options is CORRECT for every such graph \(G\)?

The correct statement is The height of \(T\) is at least 15.A BFS tree rooted at r has height equal to the largest distance from r to any vertex, the eccentricity of r. Take u, v at the maximum distance 30. Both are within distance h of the root, so\[ \begin{aligned} 30 = d(u, v) &\le d(u, r) + d(r, v) \\ &\le 2h \Rightarrow h \ge 15 \end{aligned} \]The height depends on where the BFS starts. In a graph shaped like a path of 31 vertices (with the other vertices attached near the middle), a BFS from the middle has height 15, while a BFS from an end has height 30. So 'exactly 15' and 'exactly 30' are not true for every tree, and 'at least 30' fails for the tree rooted in the middle.

Q: Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.Let \(s \in V\) be a vertex in G. For every \(u \in V\) and for every \(k \ge 0\), let \(d_{k}(u)\) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then \(d_{k}(u) = \infty\).Consider the statements:S1: For every \(k \ge 0\) and \(u \in V\), \(d_{k+1}(u) \le d_{k}(u)\).S2: For every \((u, v) \in E\), if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every \(k \ge 0\), \(d_{k}(u) \le d_{k}(v)\).Which one of the following options is correct?

Only S1 is true.S1 holds because a path of length at most k is also a path of length at most k + 1. Allowing more edges can only add candidates, so the minimum weight cannot rise: \(d_{k+1}(u) \le d_{k}(u)\).S2 fails because the shortest path through u may need more edges than a heavier path to v. Take vertices s, a, u, v with edges s-a, a-u and u-v of weight 1 and an edge s-v of weight 10. The shortest path to v is s-a-u-v (weight 3), so the edge (u, v) is part of it. For k = 1, however, u cannot be reached in one edge, so \(d_{1}(u) = \infty\), while \(d_{1}(v) = 10\) through the direct edge. Then \(d_{1}(u) \le d_{1}(v)\) is false.So S2 is not always true, which rules out the options that accept it.

Q: 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?

The most efficient algorithm runs in \(\Theta(n + m)\).Any algorithm must at least read all \(n\) lists and all \(2m\) entries, so \(\Omega(n + m)\) is a lower bound. It can be met:For each entry [\(v\)] in the list of \(u\), form the key \((\min(u,v), \max(u,v))\); the two twins of an edge get the same key.Sort all \(2m\) entries by key with a two-pass bucket (radix) sort on vertex numbers, which takes \(O(n + m)\).Twins are now adjacent in the sorted order, so one pass sets each pair of twin pointers.A hash table keyed on the vertex pair achieves the same expected bound, and memory is stated not to be a constraint. \(\Theta(n^{2})\) is what a full adjacency-matrix lookup costs, and \(\Theta(m^{2})\) comes from searching a twin’s whole list for every entry; both are slower than necessary.

Q: Let \(G\) be a weighted directed acyclic graph with \(m\) edges and \(n\) vertices. Given \(G\) and a source vertex \(s\) in \(G\), which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from \(s\) to all vertices that are reachable from \(s\) in \(G\)?

The fastest algorithm runs in Θ(m + n).In a directed acyclic graph, single-source shortest paths need no priority queue. Sort the vertices topologically (O(m + n) with depth-first search), then relax the outgoing edges of each vertex in that order. When a vertex is processed, every path into it has already been considered, because all its predecessors come earlier in the order. Each edge is relaxed once, so the total is Θ(m + n), and this works with negative edge weights too.Θ(m + n log n) is Dijkstra's algorithm with a Fibonacci heap, which ignores the acyclic structure and fails with negative weights. Θ(nm) is Bellman-Ford, for general graphs with negative edges. Θ(n3) is Floyd-Warshall, which computes all pairs.

Q: Let \(G\) be a simple undirected graph. Let \(T_{D}\) be a depth first search tree of \(G\). Let \(T_{B}\) be a breadth first search tree of \(G\). Consider the following statements.(I) No edge of \(G\) is a cross edge with respect to \(T_{D}\). (A cross edge in \(G\) is between two nodes neither of which is an ancestor of the other in \(T_{D}\).)(II) For every edge \((u,v)\) of \(G\), if \(u\) is at depth \(i\) and \(v\) is at depth \(j\) in \(T_{B}\), then \(|i - j| = 1\).Which of the statements above must necessarily be true?

Only statement I must be true.In a depth first search of an undirected graph, when an edge (u, v) is examined from u, either v is unvisited, making (u, v) a tree edge, or v was visited and is still active, making it an ancestor. So every non-tree edge joins a vertex to one of its ancestors, and there are no cross edges with respect to the DFS tree.Statement II fails. In a BFS tree the depths of the two ends of an edge differ by at most 1, but they can be equal. In a triangle with BFS from one vertex, the other two vertices are both at depth 1 and are joined by an edge, so \(|i - j| = 0\).That rules out 'II only' and 'Both I and II', and statement I being true rules out 'Neither I nor II'.

Let \(G\) be a directed graph and \(T\) a depth first search (DFS) spanning tree in \(G\) that is rooted at a vertex \(v\). Suppose \(T\) is also a breadth first search (BFS) tree in \(G\), rooted at \(v\). Which of the following statements is/are TRUE for every such graph \(G\) and tree \(T\) ?

A.There are no back-edges in \(G\) with respect to the tree \(T\)
B.There are no cross-edges in \(G\) with respect to the tree \(T\)
C.There are no forward-edges in \(G\) with respect to the tree \(T\)
D.The only edges in \(G\) are the edges in \(T\)

Exam Year(s)

GATE CS - 2024,

Answer: C

The statement that always holds is There are no forward-edges in \(G\) with respect to the tree \(T\).

A forward edge goes from a vertex u to a descendant w of u that is not its child, so w is at least two levels below u in T. In a BFS tree, every edge (u, w) satisfies depth(w) \(\le\) depth(u) + 1, because BFS reaches w no later than one step after u. Since T is a BFS tree, such an edge is impossible.

The other statements can fail. A back edge, such as an edge from a child back to v, is allowed. A cross edge is possible too: with edges v\(\to\)a, v\(\to\)b and b\(\to\)a, the tree {v\(\to\)a, v\(\to\)b} is both a DFS and a BFS tree, and b\(\to\)a is a cross edge. Those examples also show G can have edges outside T.

Discuss in Forum

Let \(G(V, E)\) be an undirected and unweighted graph with 100 vertices. Let \(d(u, v)\) denote the number of edges in a shortest path between vertices \(u\) and \(v\) in \(V\). Let the maximum value of \(d(u, v)\), \(u, v \in V\) such that \(u \ne v\), be 30. Let \(T\) be any breadth-first-search tree of \(G\). Which ONE of the given options is CORRECT for every such graph \(G\)?

A.The height of \(T\) is exactly 15.
B.The height of \(T\) is exactly 30.
C.The height of \(T\) is at least 15.
D.The height of \(T\) is at least 30.

Exam Year(s)

GATE CS - 2025,

Answer: C

The correct statement is The height of \(T\) is at least 15.

A BFS tree rooted at r has height equal to the largest distance from r to any vertex, the eccentricity of r. Take u, v at the maximum distance 30. Both are within distance h of the root, so

\[ \begin{aligned} 30 = d(u, v) &\le d(u, r) + d(r, v) \\ &\le 2h \Rightarrow h \ge 15 \end{aligned} \]

The height depends on where the BFS starts. In a graph shaped like a path of 31 vertices (with the other vertices attached near the middle), a BFS from the middle has height 15, while a BFS from an end has height 30. So 'exactly 15' and 'exactly 30' are not true for every tree, and 'at least 30' fails for the tree rooted in the middle.

Discuss in Forum

Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let \(s \in V\) be a vertex in G. For every \(u \in V\) and for every \(k \ge 0\), let \(d_{k}(u)\) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then \(d_{k}(u) = \infty\).

Consider the statements:

S1: For every \(k \ge 0\) and \(u \in V\), \(d_{k+1}(u) \le d_{k}(u)\).
S2: For every \((u, v) \in E\), if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every \(k \ge 0\), \(d_{k}(u) \le d_{k}(v)\).

Which one of the following options is correct?

A.Only S1 is true
B.Only S2 is true
C.Both S1 and S2 are true
D.Neither S1 nor S2 is true

Exam Year(s)

GATE CS - 2026,

Answer: A

Only S1 is true.

S1 holds because a path of length at most k is also a path of length at most k + 1. Allowing more edges can only add candidates, so the minimum weight cannot rise: \(d_{k+1}(u) \le d_{k}(u)\).

S2 fails because the shortest path through u may need more edges than a heavier path to v. Take vertices s, a, u, v with edges s-a, a-u and u-v of weight 1 and an edge s-v of weight 10. The shortest path to v is s-a-u-v (weight 3), so the edge (u, v) is part of it. For k = 1, however, u cannot be reached in one edge, so \(d_{1}(u) = \infty\), while \(d_{1}(v) = 10\) through the direct edge. Then \(d_{1}(u) \le d_{1}(v)\) is false.

So S2 is not always true, which rules out the options that accept it.

Discuss in Forum

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.\(\Theta(n^{2})\)
B.\(\Theta(n + m)\)
C.\(\Theta(m^{2})\)
D.\(\Theta(n^{4})\)

Exam Year(s)

GATE CS - 2016,

Answer: B

The most efficient algorithm runs in \(\Theta(n + m)\).

Any algorithm must at least read all \(n\) lists and all \(2m\) entries, so \(\Omega(n + m)\) is a lower bound. It can be met:

For each entry [\(v\)] in the list of \(u\), form the key \((\min(u,v), \max(u,v))\); the two twins of an edge get the same key.
Sort all \(2m\) entries by key with a two-pass bucket (radix) sort on vertex numbers, which takes \(O(n + m)\).
Twins are now adjacent in the sorted order, so one pass sets each pair of twin pointers.

A hash table keyed on the vertex pair achieves the same expected bound, and memory is stated not to be a constraint. \(\Theta(n^{2})\) is what a full adjacency-matrix lookup costs, and \(\Theta(m^{2})\) comes from searching a twin’s whole list for every entry; both are slower than necessary.

Discuss in Forum

Let \(G\) be a weighted directed acyclic graph with \(m\) edges and \(n\) vertices. Given \(G\) and a source vertex \(s\) in \(G\), which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from \(s\) to all vertices that are reachable from \(s\) in \(G\)?

A.\(\Theta(m + n)\)
B.\(\Theta(m + n\log(n))\)
C.\(\Theta(nm)\)
D.\(\Theta(n^{3})\)

Exam Year(s)

GATE CS - 2026,

Answer: A

The fastest algorithm runs in Θ(m + n).

In a directed acyclic graph, single-source shortest paths need no priority queue. Sort the vertices topologically (O(m + n) with depth-first search), then relax the outgoing edges of each vertex in that order. When a vertex is processed, every path into it has already been considered, because all its predecessors come earlier in the order. Each edge is relaxed once, so the total is Θ(m + n), and this works with negative edge weights too.

Θ(m + n log n) is Dijkstra's algorithm with a Fibonacci heap, which ignores the acyclic structure and fails with negative weights. Θ(nm) is Bellman-Ford, for general graphs with negative edges. Θ(n³) is Floyd-Warshall, which computes all pairs.

Discuss in Forum

Let \(G\) be a simple undirected graph. Let \(T_{D}\) be a depth first search tree of \(G\). Let \(T_{B}\) be a breadth first search tree of \(G\). Consider the following statements.

(I) No edge of \(G\) is a cross edge with respect to \(T_{D}\). (A cross edge in \(G\) is between two nodes neither of which is an ancestor of the other in \(T_{D}\).)
(II) For every edge \((u,v)\) of \(G\), if \(u\) is at depth \(i\) and \(v\) is at depth \(j\) in \(T_{B}\), then \(|i - j| = 1\).

Which of the statements above must necessarily be true?

A.I only
B.II only
C.Both I and II
D.Neither I nor II

Exam Year(s)

GATE CS - 2018,

Answer: A

Only statement I must be true.

In a depth first search of an undirected graph, when an edge (u, v) is examined from u, either v is unvisited, making (u, v) a tree edge, or v was visited and is still active, making it an ancestor. So every non-tree edge joins a vertex to one of its ancestors, and there are no cross edges with respect to the DFS tree.

Statement II fails. In a BFS tree the depths of the two ends of an edge differ by at most 1, but they can be equal. In a triangle with BFS from one vertex, the other two vertices are both at depth 1 and are joined by an edge, so \(|i - j| = 0\).

That rules out 'II only' and 'Both I and II', and statement I being true rules out 'Neither I nor II'.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Graphs and Traversals Questions and Answers || Graphs and Traversals MCQ Questions and Answers || Graphs and Traversals GK Questions and Answers || Graphs and Traversals GK MCQ Questions || Graphs and Traversals Multiple Choice Questions and Answers || Graphs and Traversals GK || GK on Graphs and Traversals || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Graphs and Traversals Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications