Kruskal Guide
Common pitfalls
A visited set is not enough
Far and away the most common pitfall in implementing Kruskal’s algorithm is believing that a “visited” set can help you figure out whether or not to use an edge.
Make sure your implementation can correctly handle the situation shown below, where the two lowest weight edges have been chosen but there are still two components that need to be connected to make the spanning tree.
Notes
- A heap can be used, but it is neither needed nor beneficial. A heap’s strength is keeping track of the smallest weight element as you add and remove elements. Kruskal’s algorithm never adds more available edges, so that strength is never used.