PRIM'S Algorithm
Prim’s algorithm produces a minimum spanning tree for a
connected weighted graph. In contrast with Kruskal's algorithm, it treats the
nodes as a single tree and keeps on adding new nodes to the spanning tree. Prim’s
algorithm is carried out by choosing an initial edge of minimum weight and successively adding
edges of minimum weight that are incident to a vertex in the tree and that do
not form simple
circuits.
{INPUT: A finite weighted connected graph G [with edges listed in any order]}
{OUTPUT: A set E of edges of a minimum spanning tree for G}
Set E :=Ø
Choose w in V(G) and set V :={w}.
while V ≠ V(G) do
Choose an edge {u,v} in E(G) of smallest possible weight with
u ϵ V(G) \ V.
Put { u,v} in E and put v in V.
return E
In the graph below the Prim's algorithm is applied:
STEP 1: Delete loops/parallel edges
STEP 2: Select any connected vertices with minimum weight. We start from y.
STEP 3: Select unvisited vertices which is adjacent of visited vertices with min weight
STEP 4: Repeat STEP 2 until all vertices are visited
Weight of the MST is: 1+2+2+1+2=8
KRUSKAL'S Algorithm
Kruskal's algorithm produces a minimum spanning tree. It treats the given graph as a forest and each of the nodes it has as a single tree. To apply this algorithm, the graph must be weighted, connected and undirected.
STEP 1: Delete loops/parallel edges
STEP 2: Sort the graph edges with respect to their weight.
XU: 1 WV: 2
YW: 1 XZ: 3
XY: 2 ZV: 3
YZ: 2 UY: 4
ZW: 2 UW: 5 XV: 6
STEP 3: Add edges to MST from smallest weight to highest. If the edges create a cycle, ignore it.
Weight of the MST is: 1+2+2+1+2=8
In Prim’s algorithm edges of minimum weight that are incident to a vertex already in the tree, and not forming a circuit, are chosen; while in Kruskal’s algorithm edges of minimum weight that are not necessarily incident to a vertex already in the tree, and that do not form a circuit, are chosen. Note that as in Prim’s algorithm, if the edges are not ordered, there may be more than one choice for the edge to add at a stage of this procedure. Consequently, the edges need to be ordered for the procedure to be deterministic.
As a result, we got the same conclusion as before using Kruskal's algorithm, but this is not going to be always the case. If edges of the graph will be unique, then the result will be the same. As Prim's algorithm will choose the lightest edge on each step, in Kruskal's unique weights give only one possible permutation of the weights.
The time complexity for these algorithms are as below:
(1) Kruskal's Algorithm: O(E log(V)), where V are nr of vertices & E nr of edges
(2) Prim's Algorithm: O(E+ V log(V)), where V are nr of vertices & E nr of edges
In (1) the most time consuming part is sorting (Disjoint-Set operations & good sorting function), meanwhile at (2) each vertex is inserted in the priority of queue only once & insertion in priority queue takes log time.
Prim's algorithms is faster in graphs with more number of edges than vertices, while Kruskal's algorithm is faster in sparse graphs, where you don't have lot of edges. Prim's alg doesn't offer much control to us over the chosen edges when we have multiple edges with the same weight. That is because only those edges that are discovered so far are stored in the queue, in difference with all the edges like in Kruskal's.
To conclude, Kruscal's algorithm looks easier in terms of implementation and offers the best control over the MST, but Prim's algorithms offers a much better complexity.
