Minimum Spanning Tree and Greedy Algorithms

Spanning Trees
MST for a connected graph
We see that it starts off with the least weighted edge and then moves in a non-decreasing way. It selects the next least weighted edge and checks for no cycle formation. This step is repeated until we have (V-1) edges.
In Prim’s Algorithm, we will start with an arbitrary node and select it. In each step, we will select a new vertex that is adjacent to the one that we have marked. Now, Prim’s algorithm will select the cheapest edge and select the vertex.

--

--

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