Spanning tree

A spanning tree of a graph is a subgraph that is a tree which contains all the vertices in the original graph. Intuitively, spanning trees are trees that "span" every vertex. Due to being trees, they use the fewest number of edges necessary to connect all the vertices.

A disconnected graph has no spanning trees. A tree is its own unique spanning tree.

To construct a spanning tree, perform a depth-first search (DFS) or breadth-first search (BFS) on the graph. Both of these algorithms will traverse the entire graph, but differ in how they prioritize which vertices get explored first.

Contents

Depth-first search

In a depth-first search, each branch of the graph is explored as deeply as possible before backtracking. The spanning tree this routine generates is as tall as possible.

algorithm dfs is
    input: a connected graph G = (V, E) and starting vertex r
    output: a spanning tree of G rooted at r

    let T be an empty graph
    explore(G, r, T)
    return T

This implementation of depth-first search has a recursive subroutine, explore:

subroutine explore is
    input: a connected graph G = (V, E), vertex to explore v, and graph T
    output: changes T

    add v to T
    for every edge (v, w) in G
        if w not in T
            add (v, w) to T
            explore(G, w, T)

⚠ The above subroutine does not return anything. It changes, or "mutates" T. By the end of all the recursive calls, T will be a spanning tree.

A non-recursive implementation of depth-first search also exists. It resembles the breadth-first search implementation below, but has one small difference that makes all the difference.

Breadth-first search

In a breadth-first search, vertices are explored in the order of their proximity to the starting vertex. The spanning tree this routine generates is as wide as possible.

algorithm bfs is
    input: a connected graph G = (V, E) and starting vertex r
    output: a spanning tree of G rooted at r

    let T be an empty graph
    add r to T
    unvisited ← []
    append r to unvisited
    while unvisited is not empty
        remove v from the front of unvisited
        for each edge (v, w) in G
            if w not in T
                add (v, w) to T
                add w to T
                append w to unvisited
    return T

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort