Kruskal's Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 15: Line 15:
<font size=-1>
<font size=-1>
  sort edges in the order of increasing cost
  sort edges in the order of increasing cost
  initialize T = ∅ <font color=teal>the tree we are growing</font>
  initialize T = ∅ <font color=teal># the tree we are growing</font>
  for edge e in the order of increasing cost:
  for edge e = (u,v) in the order of increasing cost:
   if T ⋃ e has no cycles
   if T ⋃ e has no [[Graph_Concepts#Cycles|cycles]] <font color=teal># there is no path in T from u to v</font>
     add e to T
     add e to T
</font>
</font>

Revision as of 17:15, 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

Correctness Proof

https://www.coursera.org/learn/algorithms-greedy/lecture/U3ukN/correctness-of-kruskals-algorithm

Optimized Implementation