Tutorial by Examples

In order to efficiently handle cycle detection, we consider each node as part of a tree. When adding an edge, we check if its two component nodes are part of distinct trees. Initially, each node makes up a one-node tree. algorithm kruskalMST'(G: a graph) sort G's edges by their value MST ...

The above forest methodology is actually a disjoint-set data structure, which involves three main operations: subalgo makeSet(v: a node): v.parent = v <- make a new tree rooted at v subalgo findSet(v: a node): if v.parent == v: return v return findSet(v.parent...

We can do two things to improve the simple and sub-optimal disjoint-set subalgorithms: Path compression heuristic: findSet does not need to ever handle a tree with height bigger than 2. If it ends up iterating such a tree, it can link the lower nodes directly to the root, optimizing future trav...

Sort the edges by value and add each one to the MST in sorted order, if it doesn't create a cycle. algorithm kruskalMST(G: a graph) sort G's edges by their value MST = an empty graph for each edge e in G: if adding e to MST does not create a cycle: add e to MST ...