Spanning forest

Dependencies:

  1. Forest
  2. Spanning tree

The spanning forest of an undirected graph $G$ is the union of the spanning trees of the connected components of $G$. (This means that the spanning forest of $G$ exists iff the spanning tree of every connected component exists.)

Let $F$ be a spanning forest of a weighted graph $G$. The weight of $F$, denoted as $w(F)$, is the sum of weights of edges of $F$.

A spanning forest of $G$ with minimal weight is called a minimum spanning forest of $G$. A spanning forest of $G$ with maximal weight is called a maximum spanning forest of $G$. The abbreviation MSF, which can mean either 'minimum spanning forest' or 'maximum spanning forest', is used when it is either clear from context which meaning is intended, or when it does not matter.

Dependency for:

  1. DFS on undirected graph gives spanning forest
  2. Generic Greedy MSF Growth Algorithm (GGMSFGA)
  3. Spanning forest contains all bridges
  4. Edge replacement in spanning forest using a cut

Info:

Transitive dependencies:

  1. /sets-and-relations/equivalence-classes
  2. /sets-and-relations/relation-composition-is-associative
  3. /sets-and-relations/equivalence-relation
  4. Graph
  5. Path in Graph
  6. Tree
  7. Spanning tree
  8. Forest