Discover published sets by community

An algorithm used to find the minimum spanning tree by repeatedly adding the next smallest edge that doesn’t produce a cycle until the spanning tree is complete.

A spanning tree of an undirected graph is a subgraph that includes all the vertices of the original graph, is a single connected component, and has no cycles.

A forest is a disjoint union of trees, or equivalently, an undirected graph that has no cycles. Each connected component of a forest is a tree.

The cut property holds that for any cut in the graph, if the weight of an edge in the cut-set is smaller than the weights of all other edges in the cut-set, then this edge must be part of the MST.

An algorithm that builds the minimum spanning tree by starting from an arbitrary node and repeatedly adding the smallest edge that connects a vertex in the tree to a vertex outside the tree.

The cycle property states that for any cycle in the graph, if the weight of an edge in the cycle is larger than the weights of all other edges in the cycle, then this edge cannot be part of the MST.