GATE Questions & Answers of Graph Search, Minimum Spanning Trees, Shortest Paths

What is the Weightage of Graph Search, Minimum Spanning Trees, Shortest Paths in GATE Exam?

Total 22 Questions have been asked from Graph Search, Minimum Spanning Trees, Shortest Paths topic of Algorithms subject in previous GATE papers. Average marks 1.45.

Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j| = 1.
Which of the statements above must necessarily be true?

Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y + 10z = _____.

Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.

Let G= (V,E) be any connected undirected edge-weighted graph. The weight of the edges in E are positive and distinct. Consider the following statements:

(I) Munimum Spanning Tree of G is always unique.

(II) shortest path between any two vertices of G is always unique.

Which of the above statements is/are necessarily true?

The Breadth First search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?


Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is .

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change

Q: Shortest path between any pair of vertices does not change

Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry $W_{ij}$ in the matrix W.


The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ________ .

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _______.

G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

I. If e is the lightest edge of some cycle in G, then every MST of G includes e

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

Breadth First Search(BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Let $G=\left(V,\;E\right)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $G=\left(V,\;E\right)$ let $ d\left(x\right) $ denote the shortest distance in $G$ from $s$ to $x.$ A breadth first search (BFS) is performed starting at $s.$ Let $T$ be resultant BFS tree. If $ \left(u,\;v\right) $ is an edge of $G$ that is not in $T$ , then which one of the following CANNOT be the value of $ d\left(u\right)-d\left(v\right)? $

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _______.

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes______.

Let G be a graph with n vertices and m edges.what is the tightest upper bound on the running time of depth first search on G, when G is represented as an adjecency matrix?

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtree having exactly 4 nodes is Onalogbn. Then the value of a+10b is _____.

Consider the directed graph given below.

which of the following is TRUE?

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

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.


What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and edges has time complexity