Kruskal's Runtime
How to get the next min-weight edge?
Keep edged in a (min-heap) priority queue.
How to check if adding edge (v-w) creates a cycle?
Use Union-Find to help in checking/preventing cycle
Exercise Complete the following table:
| Operation | Frequency | Cost per operation |
|---|---|---|
| build PQ | ||
| extract min | ||
| union | ||
| connected |
Solution
| Operation | Frequency | Cost per operation |
|---|---|---|
| build PQ | $1$ | $O(M)$ |
| extract min | $M$ | $O(\lg M)$ |
| union | $N$ | $O(\lg^* N)$ |
| connected | $M$ | $O(\lg^* N)$ |