Compare the Difference Between Similar Terms

Difference Between

Home / Technology / IT / General / Difference Between Kruskal and Prim

Difference Between Kruskal and Prim

March 18, 2013 Posted by Admin

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

Related posts:

Difference Between RAM and ROMDifference Between RAM and ROM Difference Between Master and Slave Difference Between Upload and Download Difference Between Multimedia and Hypermedia Difference Between Header and Footer

Filed Under: General Tagged With: Kruskal, Kruskal's Algorithm, Prim, Prim's Algorithm

About the Author: Admin

Coming from Engineering cum Human Resource Development background, has over 10 years experience in content developmet and management.

Comments

  1. Anonymous says

    April 13, 2017 at 7:58 pm

    Thank you

    Reply

Leave a Reply Cancel reply

Request Article

Featured Posts

Difference Between Coronavirus and Cold Symptoms

Difference Between Coronavirus and Cold Symptoms

Difference Between Coronavirus and SARS

Difference Between Coronavirus and SARS

Difference Between Coronavirus and Influenza

Difference Between Coronavirus and Influenza

Difference Between Coronavirus and Covid 19

Difference Between Coronavirus and Covid 19

You May Like

Difference Between Normal Red Blood Cell and Sickle Cell

Difference Between Normal Red Blood Cell and Sickle Cell

Difference Between Sexy and Beautiful

Difference Between Sexy and Beautiful

Difference Between Decibel and Hertz

Difference Between ZIP Code and Postal Code

Difference Between ZIP Code and Postal Code

Difference Between Less and Fewer

Difference Between Less and Fewer

Latest Posts

  • Difference Between Heat Flow and Heat Flux
  • Difference Between Homospory and Heterospory
  • Difference Between Chrysophytes and Euglenoids
  • Difference Between Acetone and Isopropyl Alcohol
  • Difference Between SDP and RDP
  • Difference Between Masking and Demasking Agents
  • Home
  • Vacancies
  • About
  • Request Article
  • Contact Us

Copyright © 2010-2018 Difference Between. All rights reserved. Terms of Use and Privacy Policy: Legal.