✨ Morioh

Search

SearchSearch
  • Kruskal's Algorithm
  • See also

Kruskal's Algorithm

Apr 23, 2024, 1 min read

  • #cs
  • #work/engineer-training

Kruskal’s Algorithm §


It is a minimum spanning subtree algorithm.

It performs well for sparse graphs due to simple data structures: O(​E log N).

The way it works:

  1. Choose the shortest edge.
  2. Choose the next shortest edge, ensure it does not form a cycle in the subtree formed so far. If a cycle is formed, discard the edge.
  3. Repeat step 2 until there are (N−1) edges in the subtree.

kruskals

See also §

  • Minimum Spanning Subtree
  • Trees
  • Graphs
  • Big O Notation
  • Pimm’s

Graph View

Backlinks

  • Prim's Algorithm
  • Minimum Spanning Tree

Created with Quartz v4.0.10, © 2024

  • GitHub