Kruskal vs Prim
In computer science, Prim’s and Kruskal’s algorithms are a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. A spanning tree is a subgraph of a graph such that each node of the graph is connected by a path, which is a tree. Each spanning tree has a weight, and the minimum possible weights/cost of all the spanning trees is the minimum spanning tree (MST).
More about Prim’s Algorithm
The algorithm was developed by Czech mathematician Vojtěch Jarník in 1930 and later independently by computer scientist Robert C. Prim in 1957. It was rediscovered by Edsger Dijkstra in 1959. The algorithm can be stated in three key steps;
Given the connected graph with n nodes and respective weight of each edge,
1. Select an arbitrary node from the graph and add it to the tree T (which will be the first node)
2. Consider the weights of each edge connected to the nodes in the tree and select the minimum. Add the edge and the node at the other end of the tree T and remove the edge from the graph. (Select any if two or more minimums exist)
3. Repeat step 2, until n-1 edges are added to the tree.
In this method, the tree starts with a single arbitrary node and expands from that node onwards with each cycle. Hence, for the algorithm to work properly, the graph needs to be a connected graph. The basic form of the Prim’s algorithm has a time complexity of O(V2).
More about Kruskal’s Algorithm
The algorithm developed by Joseph Kruskal appeared in the proceedings of the American Mathematical Society in 1956. Kruskal’s algorithm can also be expressed in three simple steps.
Given the graph with n nodes and respective weight of each edge,
1. Select the arc with the least weight of the whole graph and add to the tree and delete from the graph.
2. Of the remaining select the least weighted edge, in a way that not form a cycle. Add the edge to the tree and delete from the graph. (Select any if two or more minimums exist)
3. Repeat the process in step 2.
In this method, algorithm starts with least weighted edge and continues selecting each edge at each cycle. Therefore, in the algorithm the graph need not be connected. Kruskal’s algorithm has a time complexity of O(logV)
What is the difference between Kruskal’s and Prim’s Algorithm?
• Prim’s algorithm initializes with a node, whereas Kruskal’s algorithm initiates with an edge.
• Prim’s algorithms span from one node to another while Kruskal’s algorithm select the edges in a way that the position of the edge is not based on the last step.
• In prim’s algorithm, graph must be a connected graph while the Kruskal’s can function on disconnected graphs too.
• Prim’s algorithm has a time complexity of O(V2), and Kruskal’s time complexity is O(logV).