If a graph has multiple minimal spanning trees, will Kruskal and Prim’s minimal spanning tree algorithms generate the same tree?
No, it is not necessary for the Prims and Kruskals algorithms to generate the same MST. A graph can have many MSTs and both algorithms can generate different ones. But the edge types of the two MSTs will necessarily be the same. ie, if you make a multiset of the edges of the two MSTs, then the two multisets will definitely be equal. You can find a proof of this here
If a graph has multiple minimal spanning trees, how should Kruskal’s algorithm be adapted to generate all of these?
There seems to be no direct reduction of the kruskal's MST algorithm to find all the MSTs in the graph. Your best bet will be
Step1 : Sort the edges of the graph as done in kruskals.
Step2 : Now for each edge in the sorted list, two things can happen. Either the edge is in an MST or it is not. So for each edge in the sorted list, we will go over these two cases and create two new Union-Find data structures and recurse on other edges.
pseudocode:
Step1: sort edges in ascending order
Step2: now call printAllMsts(0, new UnionFind(V))
void printAllMsts(int edgeNum, UnionFind U){
if(edgeNum == edges.length){ // If no more edges to add
if(U.numEdges == V-1){ // If U has V-1 edges, then we have an MST
printMst();
}
return;
}
if(edges[edgeNum+1] == edges[edgeNum]){
printAllMsts(edgeNum+1, U); // when E is not taken in the MST
}
edge E = edges[edgeNum];
If(E can be a part of some MST){
UnionFind newU = new UnionFind(U);
newU.add(E);
}
printAllMsts(edgeNum+1, newU);
}
The running time of the algorithm will depend on the number and type of edges in the graph. The worst case input for the problem will be when all the edges in the graph are of the same length. The running time is atleast O(V*numberOfMsts) because whenever there is a possibility of different MSTs, the current Union-Find data structure is cloned which takes O(V) time.