Gate Previous Year Problems on Graph Data Structure
1. Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing. [GATE CSE 2014 Set 2]
(A) the shortest path between every pair of vertices.
(B) the shortest path from W to every vertex in the graph.
(C) the shortest paths from W to only those nodes that are leaves of T.
(D) the longest path in the graph.
Solution: Correct answer is (B)
2. Traversal of a graph is somewhat different from the tree because [GATE CSE 2006 Set 1]
(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
Solution: Correct answer is (A)
Explanation: There can be a loop in a graph, and due to this, we must maintain a visited flag for every vertex.
3. What are the suitable Data Structures for the following algorithms? [GATE CSE 2013 Set 2]
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
Solution: (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.
4. Let G be a weighted graph with edge weights greater than one and G’ be the graph constructed by squaring the weights of edges in G. LetT and T’ be the minimum spanning trees of G and G’ respectively, with total weights t and t’. Which of the following statements is TRUE? [GATE CSE 2020 ]
(A) T’ = T with total weight t’ = t^2
(B) T’ = T with total weight t’ < t^2
(C) T’ =t- T but total weight t’ = t^2
(D) None of these
Solution: (D)
5. 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
.
Solution: (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.
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? [GATE CSE 2014 ]
(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.
Solution: (C)
Explanation:
In DFS, if ‘v’ is visited
after ‘u,’ one of the following is true.
1) (u, v) is an edge.
u
/ \
v w
/ / \
x y z
2) A leaf node is ‘u.’
w
/ \
x v
/ / \
u y z
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? [GATE CSE 2014 Set 2]
(A) Only BFS
(B) Only DFS
(C) Both BFS and DFS
(D) Neither BFS nor DFS
Solution: (C)
Explanation: Both traversals can be used to see if there is a path from s to t.
8. The statement written below is true or false? [GATE CSE 2021]
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
Solution: (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.
9. Which of the condition written below is sufficient to detect a cycle in a directed graph? [GATE CSE 2008]
(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
Solution: (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.
10. 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. [GATE CSE 2014 Set 2]
(A) True
(B) False
Solution: (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.
11. Is the statement written below true or false? [GATE CSE 2015]
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
Solution: (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
Graph Data Structure Notes for GATE Exam [2024]
Graphs, a fundamental concept in computer science and mathematics, serve as powerful tools for modeling and solving a myriad of real-world problems. As aspirants gear up for the GATE Exam 2024, a comprehensive understanding of graph data structures becomes paramount. These notes aim to provide a concise and illuminating guide to graph data structures, unraveling the principles, representations, and algorithms associated with them, all of which are essential for mastering this topic in the GATE examination.
Table of Content
- What is Graph?
- Components of a Graph
- Breadth First Search or BFS in Graph
- Depth First Search or DFS in Graph
- Types of Graphs
- Representations of Graph
- Basic Properties of a Graph
- Applications of Graph Data Structure
- Advantages of Graph:
- Disadvantages of Graph
- Gate Previous Year Problems on Graph Data Structure