Algorithm Question

1. Kruskal’s algorithm will run on a disconnected graph without any problem. Just that the minimum spanning tree will be for the connected portion of graph. The disconnected vertices will not be included in the output. This is because, Kruskal’s algorithm is based on edges of the graph.The loop iterates over the sorted edges. This means that it is considering those portions of the graph that are connected through the edges and generates minimum spanning tree (MST) for the connected portion of the graph. The disconnected vertices are never considered and hence not included at all in output.

2. Let us consider the 1st implementation of Prim’s algorithm. Prim’s algorithm will go into infinite loop and can not generate MST for disconnected graphs. Look at the loop condition , it terminates when the number of vertices in the MST is the same as the number of vertices in the graph. This condition can not be achieved if the graph is disconnected . For example let’s take some vertex u already in B and a disconnected vertex v in graph . Now we can not find an minimum length edge from u (any vertex in B) to v. So v can not be included in the set B. So B will never be equal to N and the loop goes into infinite loop. Therefore Prim’s algorithm can not work on disconnected graphs as it works by considering each of the graph’ s vertices unlike Kruskal’s algorithm, which considers edges (the connected parts of graph)