Kruskal Algorithm
int MST_Kruskal (G, w)
{
A = {};
for each vertex v in G.V // O(V)
Make_Set(v);
sort all edges in G.E // O(ElogE) = O(ElogV)
for each edge(u, v) in G.E
if Find_Set(u) != Find_Set(v)
// repeate at most V-1 times
// and each time O(log(V))
A = A + {u,v};
Union(u, v);
if A == G.V
break
return A
// total complexity for Kruskal is 0(ElogV)
}
Prime Algorithm
int MST_Prime (G,w)
{
A = {};
heapE = {}; //heap for edges
A = A + {G.V[0]}, heapE.insert(G.V[0].edges); //initial
while (A != G.V){
edge(u, v) = heapE.pop(); // fiboHeap O(1)儡司， minHeap 0(logE) = 0log(V)
if v not in A{ // repeat at most V-1 times
heapE.insert(v.edges); // fiboHeap O(1), minHeap 0(logE) = O(logV)
}
}
// we can insert the valuable edges only
// so totally E inserts, V minimum choices
// total complexity for Prime is:
// 0(VlogV + E) for fiboHeap, and O(ElogV) for minHeap
}
Analysis for Prime Algorithm
Prim's algorithm select the edge with the lowest weight between the group of vortexes already selected and the rest of the vortexes. So to implement Prim's algorithm, you need a minimum heap. Each time you select an edge you add the new vortex to the group of vortexes you've already chosen, and all its adjacent edges go into the heap. Then you choose the edge with the minimum value again from the heap.
So the times we get are:
With Fibonacci heap:
Choosing minimum edge = O(time of removing minimum) = O(log(E)) = O(log(V))
Inserting edges to heap = O(time of inserting item to heap) = 1
With Min heap:
Choosing minimum edge = O(time of removing minimum from heap) = O(log(E)) = O(log(V))
Inserting edges to heap = O(time of inserting item to heap) = O(log(E)) = O(log(V))
Remember that E =~ V^2 ... so log(E) = log(V^2) = 2Log(V) = O(log(V)
In total you have E inserts, and V minimum choosings (It's a tree in the end).
So using Min heap you'll get: O(Vlog(V) + Elog(V)) = O(Elog(V))
And using Fibonacci heap you'll get: O(Vlog(V) + E)
