Simple more detailed implementationsuggest change
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 = a forest of trees, initially each tree is a node in the graph for each edge e in G: if the root of the tree that e.first belongs to is not the same as the root of the tree that e.second belongs to: connect one of the roots to the other, thus merging two trees return MST, which now a single-tree forest
Found a mistake? Have a question or improvement idea? Let me know.
Table Of Contents