Explore topic-wise InterviewSolutions in .

Correct choice is (b) It constructs MST by SELECTING edges in INCREASING order of their weights

For explanation: Prim’s algorithm can be implemented using Fibonacci heap and it NEVER accepts cycles. And Prim’s algorithm FOLLOWS greedy approach. Prim’s algorithms span from one vertex to another.

The correct answer is (a) d-ary heap

Explanation: 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. And for graphs with greater density, Prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap).

The correct option is (d) DJP ALGORITHM

Easiest explanation - The Prim’s algorithm was developed byVojtěch Jarník and it was LATTER DISCOVERED by the duo Prim and DIJKSTRA. Therefore, Prim’s algorithm is also known as DJP Algorithm.

The correct CHOICE is (b) Greedy algorithm

Easiest explanation - Prim’s algorithm uses a greedy algorithm APPROACH to find the MST of the connected WEIGHTED graph. In greedy method, we ATTEMPT to find an optimal solution in STAGES.

Right answer is (b) O(V^2)

The explanation is: Use of adjacency matrix provides the SIMPLE IMPLEMENTATION of the 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.

Right ANSWER is (a) Prim’s algorithm initialises with a VERTEX

The explanation is: Steps in Prim’s algorithm: (I) Select any vertex of 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) It MST is complete the stop, otherwise go to step (II).

The correct CHOICE is (B) False

Easiest EXPLANATION - Prim’s algorithm outperforms the Kruskal’s algorithm in case of the DENSE graphs. It is significantly FASTER if graph has more edges than the Kruskal’s algorithm.

Right answer is (C) It can accept cycles in the MST

For explanation: 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.

Correct OPTION is (b) Kruskal’s algorithm can also run on the DISCONNECTED GRAPHS

Easiest EXPLANATION - Prim’s algorithm iterates from ONE node to another, so it can not be applied for disconnected graph. 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.

The correct OPTION is (c) BE

Explanation: In Krsuskal’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, correct option is BE.

Correct answer is (b) O(E LOG V)

The explanation is: Kruskal’s algorithm involves SORTING of the edges, which takes O(E LOGE) TIME, where E is a number of edges in graph and V is the number of vertices. After sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires O(logV) time. So, overall Kruskal’s algorithm requires O(E log V) time.

Right OPTION is (c) greedy algorithm

To explain: 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.

Correct answer is (a) find minimum SPANNING tree

The best I can EXPLAIN: TheKruskal’s algorithm is used to find the minimum spanning tree of the connected graph. It construct the MST by finding the edge having the least possible weight that connects two trees in the FOREST.

Correct answer is (d) Removing one edge from the spanning tree will not make the graph disconnected

The best EXPLANATION: Every spanning tree has n – 1 EDGES 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 the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTS of the graph.

Right answer is (d) Bellman–Ford algorithm

Easiest explanation - 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.

The CORRECT option is (c) (a-d)(d-c)(d-b)(d-e)

Explanation: The minimum SPANNING TREE of the given GRAPH is shown below. It has cost 56.

The correct answer is (a) True

The BEST explanation: 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.

Right option is (c) No minimum spanning tree contains AB

Easiest explanation - Every MST will contain CD as it is 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 contains AB is false.

The CORRECT option is (c) Graph M has 3 DISTINCT MINIMUM spanning trees, each of cost 2

The best explanation: Here all non-diagonal elements in the adjacency MATRIX are 1. So, EVERY vertex is connected every other vertex of the graph. And, so graph M has 3 distinct minimum spanning trees.

The correct choice is (b) A minimum spanning TREE

To explain: In the travelling 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 a set of cities. So, travelling salesman problem can be solved by CONTRACTING the minimum spanning tree.

Right option is (c) 16

Easy explanation - 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.

The CORRECT choice is (b) False

For EXPLANATION: Minimum spanning tree is a spanning tree with the lowest cost AMONG all the spacing trees. 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.

Correct option is (d) It can be either cyclic or acyclic

Explanation: A GRAPH can have many spanning trees. Each spanning TREE of a graph G is a subgraph of the graph G, and spanning trees include every VERTEX of the GRAM. Spanning trees are always acyclic.