Posts in 2021
-
Kruskal Guide
Tuesday, December 14, 2021 in 12-14 Kruskal
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 …
-
Kruskal Algorithm
Tuesday, December 14, 2021 in 12-14 Kruskal
Make a minimal spanning tree by adding the smallest weight edge that connects two previously unconnected vertices. Count two vertices as connected if there is any path between them (not just a single edge). Code Outline We will produce a new Graph …