# 7 Difference Between Primâs And Kruskalâs Algorithm With Examples

SHARE

Aminimum spanning tree(MST) orminimum weight spanning treeis 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 aminimum 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

• 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.

## 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)

• 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

 BASIS OF COMPARISON PRIMâs ALGORITHM KRUSKALâs ALGORITHM Description This algorithm is for obtaining minimum spanning tree by selecting the adjacent vertices of already selected vertices. This algorithm is for obtaining minimum spanning tree but it is not necessary to choose adjacent vertices of already selected vertices. Initiation Primâs algorithm initiates with a node. Kruskalâs algorithm initiates with an edge. Spanning Primâs algorithms span from one node to another. Kruskalâs algorithm selects the edges in a way that the position of the edge is not based on the last step. Traversing It traverses one node more than one time to get the minimum distance. It traverses one node only once. Time Complexity 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. Kruskalâs algorithmâs time complexity is O(E log V), Where V is the number of vertices. Connected Components Primâs algorithm gives connected component as well as it works only on connected graph. Kruskalâs algorithm can generate forest (disconnected components) at any instance as well as it can work on disconnected components. Speed Primâs algorithm runs faster in dense graphs. Kruskalâs algorithm runs faster in sparse graphs.

Also Read: Difference Between RSA And DSA Algorithm

SHARE