Discover published sets by community

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.

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.

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.

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.

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.

A minimum spanning tree (MST) is a spanning tree that has the smallest possible total edge weight among all the possible spanning trees of the graph.