Difference Between Prim And Kruskal Algorithm With Examples

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is less than or equal to the weight of every other spanning tree. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree. There are two methods to find minimum Spanning Tree:

• Kruskal’s Algorithm
• Prim’s Algorithm

Prim’s Algorithm

Prim’s algorithm is used to find the minimum spanning tree from a graph. Prim’s algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized. Prim’s algorithm starts with the single node and explores all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph are selected.

Applications Of Prim’s Algorithm

• Laying cables of electrical wiring
• In network design
• Making of protocols in network cycles

Facts About Prim’s Algorithm

• This algorithm is for obtaining minimum spanning tree by selecting the adjacent vertices of already selected vertices. 
• Prim’s algorithm initiates with a node.
• Prim’s algorithms span from one node to another.
• It traverses one node more than one time to get the minimum distance.
• Prim’s algorithm has a time complexity of O(V2), Where V is the number of vertices and can be improved up to O(E + log V) using Fibonacci heaps.
• Prim’s algorithm gives connected component as well as it works only on connected graph.
• Prim’s algorithm runs faster in dense graphs.

Also Read: DDA Vs Bresenham’s Line Drawing Algorithm

Kruskal’s Algorithm 

Kruskal’s algorithm as a minimum spanning tree algorithm uses a different logic from that of Prim’s algorithm in finding the MST of a graph. Instead of starting from a vertex, Kruskal’s algorithm sorts all the edges from low weight to high and keeps adding the lowest edges, until all vertices have been covered, ignoring those edges that create a cycle. Kruskal’s algorithm follows greedy approach which finds an optimum solution at every stage of focusing on a global optimum.

Applications Of Kruskal’s Algorithm

• Electrical wiring layout
• Computer network (LAN connection)

Facts About Kruskal’s Algorithm

• This algorithm is for obtaining minimum spanning tree but it is not necessary to choose adjacent vertices of already selected vertices.
• Kruskal’s algorithm initiates with an edge.
• Kruskal’s algorithm selects the edges in a way that the position of the edge is not based on the last step.
• It traverses one node only once.
• Kruskal’s algorithm’s time complexity is O(E log V), Where V is the number of vertices.
• Kruskal’s algorithm can generate forest (disconnected components) at any instance as well as it can work on disconnected components.
• Kruskal’s algorithm runs faster in sparse graphs. 

Also Read: Difference Between Tree And Graph

Difference Between Prim’s And Kruskal’s Algorithm In Tabular Form

Also Read: Difference Between RSA And DSA Algorithm