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