10.10: Spanning Tree Algorithms

Last updated
Save as PDF

Page ID: 86162

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

Definition

Given a connected graph $G$, a spanning tree of $G$ is a subgraph of $G$ which is a tree and includes all the vertices of $G$.

We also provided the ideas of two algorithms to find a spanning tree in a connected graph.

Start with the graph connected graph $G$. If there is no cycle, then the $G$ is already a tree and we are done. If there is a cycle, let $e$ be any edge in that cycle and consider the new graph $G_1=G−e$ (i.e., the graph you get by deleting $e$). This tree is still connected since $e$ belonged to a cycle, there were at least two paths between its incident vertices. Now repeat: if $G_1$ has no cycles, we are done, otherwise define $G_2$ to be $G_1−e_1$, where $e_1$ is an edge in a cycle in $G_1$. Keep going. This process must eventually stop, since there are only a finite number of edges to remove. The result will be a tree, and since we never removed any vertex, a spanning tree.

This is by no means the only algorithm for finding a spanning tree. You could have started with the empty graph and added edges that belong to $G$ as long as adding them would not create a cycle. You have some choices as to which edges you add first: you could always add an edge adjacent to edges you have already added (after the first one, of course), or add them using some other order. Which spanning tree you end up with depends on these choices.

We now provide two algorithms that follow this latter idea of starting with an empty graph and adding edges until we have formed a tree.

Depth-first search algorithm

Input $G$, a connected graph with vertices $v_1,v_2,\ldots,v_n$
Let $T:=$tree with no edges and only the vertex $v_1$
$visit(v_1)$ (i.e. apply the procedure $visit$ to $v_1$)

VISIT

Input $v$, a vertex of a graph $G$
For each vertex $w$ adjacent to $v$ and not yet in $T$
- add vertex $w$ and edge $\{v,w\}$ to $T$
- $visit(w)$

Notice that we can pick our starting vertex arbitrarily and adjacent vertices in any order. Label the vertices in the graph below, pick a starting vertex, and use depth-first search to find a spanning tree of the graph below.

$clipboard_ef16f6ac207b1061dd74191c23b0d6952.png$

Breadth-first search algorithm

Input $G$, a connected graph with vertices $v_1,v_2,\ldots,v_n$
Let $T:=$tree with no edges and only the vertex $v_1$
Let $L:=$empty list
Put $v_1$ in $L$, a list of unprocessed vertices
While $L$ is not empty
- remove the first vertex $v$ from $L$
- for each neighbor $w$ of $v$
  - if $w$ is not in $L$ and not in $T$
    - add $w$ to the end of the list $L$
    - add $w$ and the edge $\{v,w\}$ to $T$

Using the same graph, same labels, and same starting vertex, apply the breadth-first search algorithm to find a spanning tree of the graph above.

Find a big-O estimate of the number of steps these algorithms require.

Spanning trees in weighted graphs

In the graph below, there is an oil well located at the left-most vertex, while other vertices represent storage facilities.

$clipboard_e0c64c75e16cf2f93bc1b5d04437493e4.png$

Suppose the edges represent the possible pipelines we could build, and the weight on an edge represents the cost of building that edge (in millions of dollars). Which pipelines should we build so that we can transport oil from the well to each storage facility, but we want to spend as little money as possible? What is the total cost of building these pipelines? Describe an algorithm that could be used to solve this problem.
Again, suppose the edges represent the possible pipelines we could build. Now suppose that the weight on each edge represents the time it takes for oil to get through that section of the pipeline (in hours). Which pipelines should we build so that we can transport oil from the well to each storage facility as quickly as possible? Describe an algorithm that could be used to solve this problem.

Definition

A minimum spanning tree in a connected weighted graph is a spanning tree with minimum possible total edge weight.

A shortest path spanning tree from v in a connected weighted graph is a spanning tree such that the distance from $v$ to any other vertex $u$ is as small as possible.

We present below two common algorithms used to find minimum spanning trees.

Prim's algorithm

Input: $G$, a connected weighted graph with $n$ vertices
Let $T:=$any edge with minimum weight
for $i$ from $1$ to $n-2$
- let $e:=$an edge of minimum weight among those incident to a vertex in $T$ that will not form a cycle in $T$ if added to it
- $T:=T\cup e$
Return $T$

Kruskal's algorithm

Input: $G$, a connected weighted graph with $n$ vertices
Let $T$ be an empty graph
for $i$ from $1$ to $n-1$
- let $e:=$an edge in $G$ of minimum weight among those that do not form a cycle in $T$ if added to it
- $T:=T\cup e$
Return $T$

Notice the difference between the two algorithms. In Prim's edges that are incident to a vertex already in the tree are added, while in Kruskal's the edges that are added need not be incident to a vertex already in the tree.

We now present an algorithm that creates a shortest path spanning tree from a given vertex.

Shortest path spanning tree algorithm

Input: $G$, a connected weighted graph with $n$ vertices $v_1,v_2,\ldots,v_n$and with source vertex $v_1$
Apply Dijkstra's algorithm (Section 5.7) to $G$
Let $T$ be an empty graph
For $i$ from $2$ to $n$
- Add edge $e=\{v_i,prev(v_i)\}$ to $T$
Return $T$

Search

Text Color

Text Size

Margin Size

Font Type

Spanning trees in weighted graphs