Kruskal's Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 10: | Line 10: | ||
=Overview= | =Overview= | ||
Kruskal's algorithms is a greedy algorithm that computes the [[The Minimum Spanning Tree Problem|minimum cost spanning tree]] for an undirected connected graph. It has a different approach than [[Prim%27s_Algorithm#Overview|Prim's algorithm]], in that it does not grow the connected explored territory one node at a time, but it grows the trees in parallel with a lot of simultaneous little pieces, unconnected at first, which eventually merge into the minimum cost spanning tree. It does that by sorting the edges in the ascending order of their cost, and picking edges in that order, one by one, careful not to create cycles. | Kruskal's algorithms is a greedy algorithm that computes the [[The Minimum Spanning Tree Problem|minimum cost spanning tree]] for an undirected connected graph. It has a different approach than [[Prim%27s_Algorithm#Overview|Prim's algorithm]], in that it does not grow the connected explored territory one node at a time, but it grows the trees in parallel with a lot of simultaneous little pieces, unconnected at first, which eventually merge into the minimum cost spanning tree. It does that by sorting the edges in the ascending order of their cost, and picking edges in that order, one by one, careful not to create cycles. | ||
:[[File:KruskalAlgorithm.png]] | :::[[File:KruskalAlgorithm.png]] | ||
=Non-Optimized Implementation= | =Non-Optimized Implementation= | ||
Revision as of 17:31, 22 October 2021
External
Internal
Overview
Kruskal's algorithms is a greedy algorithm that computes the minimum cost spanning tree for an undirected connected graph. It has a different approach than Prim's algorithm, in that it does not grow the connected explored territory one node at a time, but it grows the trees in parallel with a lot of simultaneous little pieces, unconnected at first, which eventually merge into the minimum cost spanning tree. It does that by sorting the edges in the ascending order of their cost, and picking edges in that order, one by one, careful not to create cycles.
Non-Optimized Implementation
Non-Optimized Implementation Running Time
sort edges in the order of increasing cost initialize T = ∅ # the tree we are growing for edge e = (u,v) in the order of increasing cost: if T ⋃ e has no cycles # there is no path in T from u to v add e to T
We can count the edges added to the spanning tree, and once we have n-1 edges, which means the spanning tree is complete, we can abort the loop.