Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024

Gate Questions on Graph Traversal-1

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

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  DFSBFS, 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. Define Graph.
    It is a non-linear data structure made up of nodes and edges. Nodes are sometimes known as vertices, while edges are lines or arcs that connect any two nodes in the network.
     
  2. What is the Breadth-First Search?
    The Breadth-First Search technique looks for a node that fulfills a set of criteria in a tree data structure. It starts at the tree's root and analyses all nodes at the current depth level before continuing to nodes at the next level.
     
  3. State the difference between a DFS Traversal and a BFS Traversal?
    In a DFS traversal of a graph, we start from any random node and travel down each branch as far as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node before visiting their children's nodes. DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
     
  4. State the difference between a tree and a graph.
    Trees and graphs are not the same since a tree can never have loops, whereas a graph can. A tree's nodes are also constantly connected, but a graph's nodes are not.
     
  5. What is a practical application of graph data structure?
    In navigation, graphs are practically used to map the shortest distance between two cities by a computer.

Conclusion

In this article, we have gone through important previous years' gate questions on graph traversal. 

Recommended problems -

 

We hope that this blog has helped you enhance your knowledge regarding gate questions on graph traversal and if you would like to know more about the preparation strategy of the gate, check out our article on gate questions on heap. Do upvote our blog to help other ninjas grow. Happy Coding!

Topics covered
1.
Introduction
2.
Previous year gate questions on graph traversal
3.
Frequently Asked Questions
4.
Conclusion