Question 1:
Let G=(V,E) be a connected undirected graph with distinct weights on edges. Consider
running BFS and DFS on G from a vertex s. Let TBFS and TDFS denote the spanning trees
formed.
Which of the following must always be true?
A. The set of vertices in TBFS and TDFS are the same.
B. The number of edges in TBFS and TDFS is equal.
C. If G is a tree, then TBFS =TDFS
D. If edge weights are considered, BFS might fail to produce shortest-weight paths.
Question 2 :
Let G=(V,E) be a directed acyclic graph (DAG). We define G′ to be the reverse of G, i.e., for
every edge (u,v)∈E, (v,u)∈E′.
Let BFS be run on both G and G′ from a vertex s, and let D and D′ be the set of distance
values in the two cases. Assume the same vertex ordering.
Which of the following is always true?
A. D[v]≤D′[v] for all v∈V
B. D[v]=D′[v] for all v∈V
C. There exists a DAG where D[v]>D′[v] for some v∈V
D. There exists a DAG where D[v]<D′[v] for some v∈V
Question 3 :
Given a directed graph with n vertices and m edges, simulate DFS such that whenever a
vertex is finished (i.e., after all neighbors are visited), it is pushed onto a stack only if the
vertex number is even.
Assume traversal is done in increasing order of vertices. How many vertices can never be
pushed to the stack regardless of edge orientation?
Question 4 :
Let G=(V,E) be a connected directed graph with a path P=(v1 →v2 →⋯→vk ). If DFS is
performed from v1 , and every time a vertex is visited we reverse all outgoing edges of that
vertex (i.e., (u,v) becomes (v,u)), which of the following is guaranteed?
A. DFS will terminate in fewer than k steps
B. DFS may enter infinite loop even in a finite DAG
C. Final DFS tree will be a linear chain
D. DFS may not visit all vertices reachable from v1 in G
Question 5 :
Let a graph G=(V,E) be encoded using a custom hash-based adjacency function
h(u,v)=(u⋅v)modk. Each time BFS explores an edge (u,v), it only follows it if h(u,v) is even.
Assume k=7. Let G have vertices from 1 to 7, with all possible edges (complete graph).
Starting BFS from vertex 1, which of the following are guaranteed truths?
A. BFS may skip visiting certain vertices even if they are directly connected
B. BFS tree depends on the hash function modulo k
C. The resulting BFS tree will always have 6 edges
D. It is possible for some vertices to be unreachable from 1
Question 6 :
Given a directed graph G=(V,E), perform a modified BFS starting from vertex s, where:
• When a vertex u is dequeued, and an adjacent vertex v is found,
• The edge (u,v) is deleted,
• A new edge (v,u) is added in place.
Assuming G has n nodes and forms a simple cycle, how many vertices will be reachable
from s after BFS terminates?
A. 1
𝑛
B. ⌊ 2 ⌋
C. n
D. Depends on whether n is even or odd
Question 7 :
In a DFS run on a graph G, for each vertex u, we store d[u] = discovery time and f[u] =
finishing time.
Suppose for all u∈V, we find that d[u] + f[u] = T for a fixed constant T. What is the
value of T for a graph with n vertices?
Give the answer in terms of n.
Question 8 :
Let an undirected graph G be represented using an adjacency matrix A such that:
• A[i][j]=1 if there is an edge between vertex i and j,
• A[i][j]=2 if this edge was visited during DFS traversal from i to j,
• All other entries remain unchanged.
After DFS completes from source vertex 1, which of the following must be true?
A. A[i][j]=A[j][i]=2 for all tree edges
B. There must exist at least one A[i][j]=1 which was never visited
C. The number of entries equal to 2 is exactly 2(n−1)
D. The sum of all entries in matrix A is at most 2m, where m is the number of edges
Question 9:
Let G be a direted graph where every vertex has out-degree exactly 1. Let DFS be run
starting from every vertex.
Which of the following statements is always true?
A. Every edge is either a back edge or a cross edge
B. DFS tree will contain exactly one tree edge per component
C. The total number of back edges equals the number of cycles
D. Forward edges are never formed in such graphs
Question 10 :
In the standard BFS algorithm, each vertex has a color: WHITE (unvisited), GRAY
(discovered but not finished), BLACK (finished). Suppose we’re asked to reduce space and
encode this color with a single boolean bit per node.
Which of the following tricks allow this compression without changing the correctness of
BFS?
A. Replace BLACK with “bit = 1” and GRAY/WHITE with “bit = 0”
B. Maintain an external level array and skip re-processing nodes already assigned a level
C. Delay coloring to BLACK until dequeuing from the queue
D. Use distance value alone to distinguish processed vs. unprocessed nodes
