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)
|