# Minimum Spanning Tree MCQ

1. Which of the following is false in the case of a spanning tree of graph G?

a) It is a tree that spans G

b) It is a subgraph of the G

c) It includes every vertex of the G

d) It can be either cyclic or acyclic

Answer: d

A graph can have many spanning trees. Each spanning tree of graph G is a subgraph of graph G, and spanning trees includes every vertex of the gram. Spanning trees are always acyclic.

2. Every graph has many minimum spanning trees.

a) True

b) False

Answer: a

A minimum spanning tree is a spanning tree with the lowest cost among all the spacing trees. The Sum of all of the edges in the spanning tree is the cost of the spanning tree. There can be many minimum spanning trees for a given graph.

3. Consider a complete graph G with 4 vertices. Graph G has ____ spanning trees.

a) 15

b) 8

c) 16

d) 13

Answer: c

A graph can have many spanning trees. And a complete graph with n vertices has n(n-2) spanning trees. So, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees.

4. The traveling salesman problem can be solved using _________

a) A spanning tree

b) A minimum spanning tree

c) Bellman-Ford algorithm

d) DFS traversal

Answer: b

In the traveling salesman problem, we have to find the shortest possible route that visits every city exactly once and returns to the starting point for the given set of cities. So, the traveling salesman problem can be solved by contracting the minimum spanning tree.

5. Which of the following is false about the minimum spanning tree?

a) The spanning trees do not have any cycles

b) MST has n – 1 edge if the graph has n edges

c) Edge e belongs to a cut of the graph if has a weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph

d) Removing one edge from the spanning tree will not make the graph disconnected

Answer: d

Every spanning tree has n – 1 edge if the graph has n edges and has no cycles. The MST follows the cut property, Edge e belonging to a cut of the graph if has a weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph.

6. Consider an undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has a distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?

a) Every minimum spanning tree of G must contain CD

b) If AB is in a minimum spanning tree, then its removal must disconnect G

c) No minimum spanning tree contains AB

d) G has a unique minimum spanning tree

Answer: c

Every MST will contain CD as it is the smallest edge. So, Every minimum spanning tree of G must contain CD is true. And G has a unique minimum spanning tree is also true because the graph has edges with distinct weights. So, no minimum spanning tree containing AB is false.

7. If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.

a) True

b) False

Answer: a

A subgraph is a graph formed from a subset of the vertices and edges of the original graph. And the subset of vertices includes all endpoints of the subset of the edges. So, we can say MST of a graph is a subgraph when all weights in the original graph are positive.

8. Which of the following is not the algorithm to find the minimum spanning tree of the given graph?

a) Boruvka’s algorithm

b) Prim’s algorithm

c) Kruskal’s algorithm

d) Bellman-Ford algorithm

Answer: d

The Boruvka’s algorithm, Prim’s algorithm, and Kruskal’s algorithm are the algorithms that can be used to find the minimum spanning tree of the given graph.

The Bellman-Ford algorithm is used to find the shortest path from the single source to all other vertices.

9. Consider graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true?

a) Graph M has no minimum spanning tree

b) Graph M has a unique minimum spanning trees of cost 2

c) Graph M has 3 distinct minimum spanning trees, each of which costs 2

d) Graph M has 3 spanning trees of different costs

**Answer. C**

Here all non-diagonal elements in the adjacency matrix are 1. So, every vertex is connected to every other vertex of the graph. And, so graph M has 3 distinct minimum spanning trees.

8. Consider the graph shown below. Which of the following are the edges in the MST of the given graph?

a) (a-c)(c-d)(d-b)(d-b)

b) (c-a)(a-d)(d-b)(d-e)

c) (a-d)(d-c)(d-b)(d-e)

d) (c-a)(a-d)(d-c)(d-b)(d-e)

**Answer. C. (a-d)(d-c)(d-b)(d-e)**

The minimum spanning tree of the given graph is shown below. It cost 56.

(a-d)(d-c)(d-b)(d-e) are the edges in the MST of the given graph

1. Kruskal’s algorithm is used to ______

a) find minimum spanning tree

b) find a single source shortest path

c) find all pair shortest path algorithm

d) traverse the graph

Answer: a

Kruskal’s algorithm is used to find the minimum spanning tree of the connected graph. It constructs the MST by finding the edge having the least possible weight that connects two trees in the forest.

2. Kruskal’s algorithm is a ______

a) divide and conquer algorithm

b) dynamic programming algorithm

c) greedy algorithm

d) approximation algorithm

Answer: c

Kruskal’s algorithm uses a greedy algorithm approach to find the MST of the connected weighted graph. In the greedy method, we attempt to find an optimal solution in stages.

3. Consider the given graph.

What is the weight of the minimum spanning tree using Kruskal’s algorithm?

a) 24

b) 23

c) 15

d) 19

Answer: d

Kruskal’s algorithm constructs the minimum spanning tree by constructing by adding the edges to the spanning tree one-one by one. The MST for the given graph is,

So, the weight of the MST is 19.

4. What is the time complexity of Kruskal’s algorithm?

a) O(log V)

b) O(E log V)

c) O(E2)

d) O(V log E)

Answer: b

Kruskal’s algorithm involves sorting of the edges, which takes O(E logE) time, where E is the number of edges in the graph and V is the number of vertices.

After sorting, all edges are iterated and the union-find algorithm is applied. union-find algorithm requires O(logV) time. So, overall Kruskal’s algorithm requires O(E log V) time.

5. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?

a) GF

b) DE

c) BE

d) BG

Answer: c

In Kruskal’s algorithm, the edges are selected and added to the spanning tree in increasing order of their weights. Therefore, the first edge selected will be the minimal one. So, the correct option is BE.

6. Which of the following edges form a minimum spanning tree on the graph using Kruskal’s algorithm?

a) (B-E)(G-E)(E-F)(D-F)

b) (B-E)(G-E)(E-F)(B-G)(D-F)

c) (B-E)(G-E)(E-F)(D-E)

d) (B-E)(G-E)(E-F)(D-F)(D-G)

Answer: a

Using Krushkal’s algorithm on the given graph, the generated minimum spanning tree is shown below.

So, the edges in the MST are, (B-E)(G-E)(E-F)(D-F).

7. Which of the following is true about minimum spanning trees?

a) Prim’s algorithm can also be used for disconnected graphs

b) Kruskal’s algorithm can also run on the disconnected graphs

c) Prim’s algorithm is simpler than Kruskal’s algorithm

d) In Kruskal’s sort edges are added to MST in decreasing order of their weights

Answer: b

Prim’s algorithm iterates from one node to another, so it can not be applied to disconnected graphs. Kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest. Kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm.

8. Which of the following is false about Kruskal’s algorithm?

a) It is a greedy algorithm

b) It constructs MST by selecting edges in increasing order of their weights

c) It can accept cycles in the MST

d) It uses a union-find data structure

Answer: c

Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. So, using Kruskal’s algorithm is never formed.

9. Kruskal’s algorithm is best suited for dense graphs than the prim’s algorithm.

a) True

b) False

Answer: b

Prim’s algorithm outperforms Kruskal’s algorithm in the case of dense graphs. It is significantly faster if the graph has more edges than Kruskal’s algorithm.

10. Consider the following statements.

S1. Kruskal’s algorithm might produce a non-minimal spanning tree.

S2. Kruskal’s algorithm can efficiently be implemented using the disjoint-set data structure.

a) S1 is true but S2 is false

b) Both S1 and S2 are false

c) Both S1 and S2 are true

d) S2 is true but S1 is false

Answer: d

In Kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. And Kruskal’s algorithm always finds the MST for the connected graph.

1. Which of the following is true about Prim’s algorithm?

a) Prim’s algorithm initializes with a vertex

b) Prim’s algorithm initializes with an edge

c) Prim’s algorithm initializes with a vertex that has the smallest edge

d) Prim’s algorithm initializes with a forest

Answer: a

Steps in Prim’s algorithm:

(I) Select any vertex of a given graph and add it to MST

(II) Add the edge of minimum weight from a vertex not in MST to the vertex in MST

(III) If MST is complete stop, otherwise, go to step (II).

2. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?

a) O(log V)

b) O(V^{2})

c) O(E^{2})

d) O(V log E)

Answer: b

The use of an adjacency matrix provides the simple implementation of Prim’s algorithm.

In Prim’s algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity will be O(V^{2}), where V is the number of vertices.

3. Prim’s algorithm is a ______

a) Divide and conquer algorithm

b) Greedy algorithm

c) Dynamic Programming

d) Approximation algorithm

Answer: b

Prim’s algorithm uses a greedy algorithm approach to find the MST of the connected weighted graph. In the greedy method, we attempt to find an optimal solution in stages.

4. Prim’s algorithm resembles Dijkstra’s algorithm.

a) True

b) False

Answer: a

In Prim’s algorithm, the MST is constructed starting from a single vertex and adding new edges to the MST that link the partial tree to a new vertex outside of the MST.

Dijkstra’s algorithm also relies on a similar approach to finding the next closest vertex. So, Prim’s algorithm resembles Dijkstra’s algorithm.

5. Kruskal’s algorithm is best suited for sparse graphs than the prim’s algorithm.

a) True

b) False

Answer: a

Prim’s algorithm and Kruskal’s algorithm perform equally in the case of sparse graphs. But Kruskal’s algorithm is simpler and easy to work with. So, it is best suited for sparse graphs.

6. Prim’s algorithm is also known as __________

a) Dijkstra–Scholten algorithm

b) Borůvka’s algorithm

c) Floyd–Warshall algorithm

d) DJP Algorithm

Answer: d

Prim’s algorithm was developed by Vojtěch Jarník and it was later discovered by the duo Prim and Dijkstra. Therefore, Prim’s algorithm is also known as DJP Algorithm.

7. Prim’s algorithm can be efficiently implemented using ________ for graphs with greater density.

a) d-ary heap

b) linear search

c) Fibonacci heap

d) binary search

Answer: a

In Prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. This searching can be efficiently implemented using binary heap for dense graphs.

For graphs with greater density, Prim’s algorithm can be made to run in linear time using the d-ary heap (a generalization of the binary heap).

8. Which of the following is false about Prim’s algorithm?

a) It is a greedy algorithm

b) It constructs MST by selecting edges in increasing order of their weights

c) It never accepts cycles in the MST

d) It can be implemented using the Fibonacci heap

Answer: b

Prim’s algorithm can be implemented using the Fibonacci heap and it never accepts cycles. And Prim’s algorithm follows a greedy approach. Prim’s algorithms span from one vertex to another.