Minimum Spanning Tree — Prim’s and Kruskal’s algorithm

What is a spanning tree?

  1. has n vertices
  2. has n - 1 edge
  3. is connected

Note

What is a minimum spanning tree?

|E|C|V|- 1 - cycles

Prims’s Algorithm

Algorithm

  1. Initialize the minimum spanning tree with a vertex chosen at random.
  2. Find all the edges that connect the tree to new adjacent vertices, find the minimum among them and add it to the tree.
  3. Repeat step 2 until we get a minimum spanning tree.

Pseudo Code

Code

Kruskal’s Algorithm

Note

Algorithm

  1. Sort all the edges in the ascending order of weight.
  2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then remove the edge.
  3. Keep adding edges until we reach all vertices i.e., get a minimum spanning tree.

Pseudo Code

Code

Note

examples of sparse and dense graph

Differences between Prim’s and Kruskal’s algorithm

  1. As we discussed early on, Prim’s algorithm can only generate a connected graph component thus it works only on a connected graph. Whereas Kruskal’s algorithm can generate forest ( disconnected components), it can work on disconnected graphs.
  2. When to use Prim’s and when to use Kruskal’s? Due to each algorithm's nature, we can say that Prim’s algorithm runs faster in dense graphs whereas Kruskal’s algorithm runs faster in a sparse graph. Why is it so? Prim’s algorithm runs better in a dense graph as it only compares a limited number of edges per loop, whereas Kruskal’s algorithm starts by sorting all edges in the list when going through them again to check if the edge is part of MST or not. While both algorithms have similar running times, the number of edges in the graph should be the main component when you are deciding between the algorithms. More edges compared to vertices, use Prim’s otherwise go with Kruskal’s.

So, where to go from here?

References

  1. https://www.youtube.com/watch?v=4ZlRH0eK-qQ
  2. https://d3gt.com/unit.html?spanning-tree
  3. https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/
  4. https://stackoverflow.com/questions/53475447/understanding-when-to-use-prim-or-kruskal-for-minimum-spanning-tree
  5. https://www.geeksforgeeks.org/difference-between-prims-and-kruskals-algorithm-for-mst/
  6. https://en.wikipedia.org/wiki/Prim%27s_algorithm
  7. https://personal.utdallas.edu/~besp/teaching/mst-applications.pdf
  8. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/prim2.html

My Github Repository

  1. https://github.com/Sethuram52001/DSA

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Looking for an API to get Gold and Silver live rates in Qatari RiYal? Check this company

Enabling Partial Refund on GoBiz & GoFood Service — a UX Case Study

Take away: Infrastructure talk with Kief Morris

PAGE 1 : ELK HILLS

What Is IAB Taxonomy Categorization And How To Obtain It

READ/DOWNLOAD!<

Day 8: Finally Began The UI

Getting understand of S.O.L.I.D. (For English Readers)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sethuram.S.V

Sethuram.S.V

More from Medium

Greedy Algorithms

LeetCode — Linked List Cycle

Interval Scheduling Greedy Algorithm

Print Spiral Matrix in O(n) time & O(1) space