[prev] 31 [next]

Implementation of Kruskal's Algorithm (cont)

Rough cost analysis:
  • sorting edge list is O(E log E)
  • at least V iterations over sorted edges
  • on each iteration ...
    • getting next lowest cost edge is O(1)
    • checking whether adding it forms a cycle: cost = ??
Possibilities for cycle checking:
  • use DFS ... too expensive?
  • use Union-Find data structure (see Sedgewick ch.1)