## 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 Structure____s__ 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.