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

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 ona binary tree beginning from the root vertex. There is a vertext 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 = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x V, let d(x) 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 (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) - d(v)?

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