COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Maximum spanning tree
|
|
|
Spanning tree
|
|
|
Minimum spanning tree
|
|
|
None
|
Detailed explanation-1: -Prim’s and Kruskal’s algorithm both produce the minimum spanning tree.
Detailed explanation-2: -We conclude that Prim’s and Kruskal’s algorithms are greedy algorithms used for finding the minimum spanning tree of a given weighted graph. Prim’s algorithm adds nodes while Kruskal’s algorithm adds edges which calculates the minimum spanning tree.
Detailed explanation-3: -Prim’s and Kruskal’s algorithms will always return the same Minimum Spanning tree (MST). Prim’s algorithm for computing the MST only work if the weights are positive. An MST for a connected graph has exactly V-1 edges, V being the number of vertices in the graph.
Detailed explanation-4: -Prim’s algorithm is used to find the Minimum Spanning Tree for a given graph.
Detailed explanation-5: -Both Prim’s and Kruskal’s algorithm work with negative edge weights. It is because the correctness of the algorithm does not depend on the weights being positive.