Prim’s and Kruskal’s algorithms are designed for finding the minimum spanning tree of a graph. These algorithms use a different approach to solve the same problem. Prim’s algorithm works by selecting the root vertex in the beginning and then spanning from vertex to vertex adjacently, while in Kruskal’s algorithm the lowest cost edges which do not form any cycle are selected for generating the MST. These algorithms are designed for the undirected graph.
The Minimum Spanning Tree (MST) is a graph whose word is to determine the lowest cost edges within a single connected component. It is implemented in various applications such as in wiring scheme for the telephone network, LDPC codes for error correction cluster analysis, finding the road networks (specifically in network design). It also proves that greedy solution can probably give an optimal solution of the problem.
Content: Prim’s Algorithm Vs Kruskal’s Algorithm
Comparison Chart
| Basis for comparison | Prims Algorithm | Kruskal algorithm |
|---|---|---|
| Basic | The algorithm obtains the minimum spanning tree by choosing the adjacent vertices from a set of selected vertices. | To obtain the minimum spanning tree this algorithm select the edges from a set of edges. |
| Selection of the route is based on | Vertices | Edges |
| Connected components | All the graph components must be connected. | Disconnected graph may present. |
| Speed | Better for the dense graph. | Good for the sparse graph. |
| Time complexity | O(V2) | O(log V) |
| Initiates with | A node. | An edge. |
| Adjacent vertices | Must be opted for the tree. | Selected vertices are not necessarily adjacent. |
Definition of Prim’s Algorithm
The Prim’s algorithm searches for the minimum spanning tree for the connected weighted graph which does not have cycles. The algorithm was devised by Vojtek Jarnik in 1938, later it was rediscovered by Robert Prim. The algorithm works by initially choosing a root node r, then expands along the adjacent vertices by choosing the minimum weight edges and the process is repeated until all the vertices are visited. The prim’s algorithm has O(log V2) time complexity in the worst case. It forms a single tree out of the set of edges having least cost. The algorithm follows the greedy strategy where at each step the tree expands with the addition of a new least weighted edge possible.
The prim’s algorithm works well with the dense graph (Graph having a large number of edges). It only produces the connected tree. There can be three types of vertices included in the algorithm: tree vertices, fringe vertices and unseen vertices. Tree vertices are the type of vertices which are the part of the minimum spanning tree ‘T’. Fringe vertices are adjacent vertices of tree vertex but are not a part of ‘T’. Unseen vertices are not included in any of the above category (tree and fringe).
Steps involved in a Prim’s Algorithm
- Select a root vertex.
- Choose an edge having the lowest weight and which connects the tree and fringe vertex.
- Include the recently selected vertex and edge to the minimum spanning tree T.
- Repeat the step 2 and step 3 until n-1 (where n is the number of vertices) edges are added in the MST.
Definition of Kruskal’s Algorithm
Kruskal’s algorithm is another greedy approach to produce the MST (Minimum Spanning Tree). It was developed by Joseph Kruskal. The objective of the algorithm is to find the subset of the graph where every vertex is included. It works by initially treating each node as ‘n’ number of distinct partial trees. After performing each consecutive step, two disjoint partial trees are connected into a single partial tree through an edge having the minimum weight. The edge is added if it does not form any cycles. This process is repeated until n-1 iterations.
The time complexity of the algorithm is O(log V). There is no compulsion of producing a connected graph. The generating minimum spanning tree can be disconnected, and in that case, it is known as minimum spanning forest. A forest is a combination of trees. Kruskal’s algorithm is preferred when the graph is sparse i.e. it consists of less number of edges.
Steps involved in the Kruskal’s Algorithm
- A forest of m number of trees is created.
- Select a minimum cost edge that connects two trees without forming any cycle.
- Delete the added edge form the list.
- Repeat the actions till (n-1) edges are added.
Key Differences Between Prim’s and Kruskal’s Algorithm
- Prim’s algorithm works by choosing the adjacent vertices from the selected set of vertices. In contrast, the Kruskal’s algorithm selects least weight edges instead of using adjacency list, it organizes the edges by their weights.
- The generation of minimum spanning tree in Prim’s algorithm is based on the selection of graph vertices and it initiates with vertex whereas in Kruskal’s algorithm it depends on the edges and initiates with an edge.
- Prim’s algorithm always generates MST with connected components while this is not the case in Kruskal’s algorithm where the MST may not have connected components (i.e. Minimum spanning forest).
- Kruskal’s algorithm works at a faster pace in the sparse graph. As against, Prim’s algorithm performs better in the dense graph.
- The time complexity of Prim’s algorithm is O(V2). Conversely, Kruskal’s algorithm runs in O(log V) time.
- In Prim’s algorithm, the adjacent vertices must be selected whereas Kruskal’s algorithm does not have this type of restrictions on selection criteria.
Example of Prim’s Algorithm
Let us find the Minimum Spanning Tree of the following graph using Prim’s algorithm.
The step by step pictorial representation of the solution is given below.
Example of Kruskal’s Algorithm
Let’s take the same graph for finding Minimum Spanning Tree with the help of Kruskal’s algorithm. The following figure shows the step by step formation of the MST implementing Kruskal’s algorithm.
Conclusion
The performance of the two algorithms could differ depending upon the certain factors such as the number of vertices. Prim’s algorithm runs in O(V2) time and works well in the massive graphs while Kruskal’s algorithm consumes O(log V) and perform suitably with small graphs. Although, among both of the algorithm Kruskal’s algorithm can generate better results.
Leave a Reply