Introduction
Graph traversal is the process of exploring each vertex in a graph. Every graph problem involves traversing in some form. It's frequently necessary to keep track of visited vertices to avoid becoming stuck in cycles. It would be helpful to practice and check what type of gate questions on graph traversals have come before the gate exam.
You can check out our Graph blogs to learn more about the graph.
This blog covers the previous year's gate questions on Graph Traversal (related to the topic of Graph traversal).
Previous year gate questions on graph traversal
Following are the previous year's gate questions on graph traversals:
1. Traversal of a graph is somewhat different from the tree because
(A) There can be a loop in a graph, so we must maintain a visited flag for every vertex
(B) DFS of a graph uses the stack, but the inorder traversal of a tree is recursive
(C) BFS of a graph uses a queue, but a time-efficient BFS of a tree is recursive.
(D) All of the above
Answer: (A)
Explanation: There can be a loop in a graph, and due to this, we must maintain a visited flag for every vertex. You can visit depth-first search-dfs to learn more.
2. Which of the algorithms given below can be used to most efficiently determine the presence of a cycle in a given graph?
(A) Breadth-First Search
(B) Depth First Search
(C) Prim's Minimum Spanning Tree Algorithm
(D) Kruskal's Minimum Spanning Tree Algorithm
Answer:(A) and (B)
Explanation: Using DFS Algorithm or bfs algorithm, time complexity: O(V+E) and space complexity: O(V) are the most efficient algorithm among the given options. Visit DFS, BFS, and graph-traversal-techniques-in-dfs-bfs to learn more.
3. The Breadth-First Search algorithm has been implemented with the help of a queue. What is a possible order of visiting the nodes of the following graph is
(A) NQMPOR
(B) QMNPOR
(C) QMNPRO
(D) MNOPQR
Answer: (C)
Explanation: Option (A) is NQMPOR. It cannot be BFS because P is visited before O here.
Option (D) is MNOPQR. It cannot be a BFS because the traversal begins with M, but O has been visited before N and Q.
In BFS, every adjacent must be called before adjacent of adjacent.
(B) and (C) correspond to QMNP. Before N and P, M had been added to the queue (because M comes before NP in QMNP). R is placed in the line before N and P's neighbors because it is M's neighbor (which is O). As a result, R is visited first, followed by O.
4. What are the suitable Data Structures for the following algorithms?
1) Breadth-First Search
2) Depth First Search
3) Prim's Minimum Spanning Tree
4) Kruskal's Minimum Spanning Tree
(A)
1) Stack
2) Queue
3) Priority Queue
4) Union Find
(B)
1) Queue
2) Stack
3) Priority Queue
4) Union Find
(C)
1) Stack
2) Queue
3) Union Find
4) Priority Queue
(D)
1) Priority Queue
2) Queue
3) Stack
4) Union Find
Answer: (B)
Explanation: 1) Queue is used in Breadth-First Search
2) Stack is used in depth-first search-dfs
3) Priority Queue is used in Prim's Minimum Spanning Tree.
4) Union Find is used in Kruskal's Minimum Spanning Tree.
5. Consider the following graph,
Among the following sequences:
(I) a b e g h f
(II) a b f e h g
(III) a b f h g e
(IV) a f g h b e
Which are the depth-first traversals of the above graph?
(A) I, II, and IV only
(B) I and IV only
(C) II, III, and IV only
(D) I, III, and IV only
Answer: (D)
Explanation: We can check all DFSs for these features.
In DFS, if a 'v' vertex is visited
after 'u,' one of the following is true.
1) (u, v) is an edge.
2) 'u' is a leaf node.
.
In DFS, after we have visited a node, we first go back to all children who were not visited. If no children are left unvisited (u is a leaf), then control goes back to the parent, and the parent then visits the subsequent unvisited children.
6. Let G be an undirected graph. Consider a depth-first traversal of G, where T is the depth-first search tree that results. Let u be the first new (unvisited) vertex visited after u in the traversal, and v be its first new (unvisited) vertex visited after u. Which of the assertions below is always true?.
(A) In G, u,v must be an edge, while in T, u is a descendent of v.
(B) In G, u,v must be an edge, while in T, v is a descendent of u.
(C) If u,v in G is not an edge, then u in T is a leaf
(D) If u,v in G is not an edge, then u and v in T must have the same parent.
Answer: (C)
Explanation:
In DFS, if 'v' is visited
after 'u,' one of the following is true.
1) (u, v) is an edge.
2) A leaf node is 'u.'
In DFS, after we have visited a node, we first go back to all children who were not visited. If no children are left unvisited(u is a leaf), then control goes back to the parent, and the parent then visits the subsequent unvisited children.
7. Which of the two traversals (BFS and DFS) may be used to find if there is a path from s to t given two vertices in a graph s and t?
(A) Only BFS
(B) Only DFS
(C) Both BFS and DFS
(D) Neither BFS nor DFS
Answer: (C)
Explanation: Both traversals can be used to see if there is a path from s to t.
8. Make a software that creates executable programs and libraries from source code by reading makefiles, which indicate how to generate the target program and which of the following standard graph algorithms Make uses.
(A) Strongly Connected Components
(B) Dijkstra's Shortest Path
(C) Topological Sorting
(D) Breadth-First Search
Answer: (C)
Explanation: Topological sorting can determine the order in which software is built. It is decided by Make software. Topological sorting determines the order by considering the dependencies specified in the makefile. For learning more about Topological sorting visit Topological Sorting blog.
9. The statement written below is true or false?
If a directed graph's DFS contains a back edge, any other directed graph's DFS will also have at least a single back edge.
(A) True
(B) False
Answer: (A)
Explanation: A cycle in the graph is called its back edge. So if we get a cycle, all DFS traversals would contain at least one back edge.
10. Which of the condition written below is sufficient to detect a cycle in a directed graph?
(A) There is an edge from a currently visited node to an already seen node.
(B) There is an edge from the currently visited node to an ancestor of the currently visited node in the forest of DFS.
(C) Every node is seen two times in DFS.
(D) None of the above
Answer: (B)
Explanation: If there is an edge from the currently visited node to an ancestor of the currently visited node in the forest of DFS, it means a cycle is formed. As this is an apparent condition about cycle formation, so this condition is sufficient. Visit Detect Cycle in a Graph to learn more.
11. If the finishing time f[u] > f[v] of DFS for two vertices u and v in a graph G which is directed, and u and v are in the DFS tree same as each other in the DFS forest, then u is an ancestor of v in the depth-first tree.
(A) True
(B) False
Answer: (B)
Explanation: In a graph that contains three nodes, r u and v, with edges (r; u) and (r; v), and r is the starting point for the DFS, u and v are siblings in the DFS tree; neither as the ancestor of the other.
12. Is the statement written below true or false?
A DFS of a directed graph generally produces the exact number of edges of a tree, i.e., not dependent on the order in which vertices are considered for DFS.
(A) True
(B) False
Answer: (B)
Explanation: Consider the following graph. If we start from 'a', then there is one tree edge. If we start from 'b,' there is no tree edge.
a—->b
13. Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following options is NOT a topological ordering?
(A) 1 2 3 4 5 6
(B) 1 3 2 4 5 6
(C) 1 3 2 4 6 5
(D) 3 2 4 1 6 5
Answer: (D)
Explanation: In option D, one appears after 2 and 3, which is impossible in Topological Sorting
Refer to Gate Questions on Gate Questions on Graph Traversal- 2 for more questions.
84+ registered 