[prev] 47 [next]

Kruskal's Algorithm (cont)

Time complexity analysis …
  • sorting edge list is O(E·log E)
  • min V, max E iterations over sorted edges
  • on each iteration …
    • getting next lowest cost edge is O(1)
    • checking whether adding it forms a cycle: cost = ??
      • use DFS … too expensive?
      • could use Union-Find data structure (see Sedgewick Ch.1) to maintain sets of connected components
        ⇒ loop is O(E·log V)
  • overall complexity O(E·log E) = O(E·log V)