---
tags: Data structure and algorithm
---
# Graph -- Spanning Tree
## Relative articles
1. [Graph -- Basic concept](https://hackmd.io/@Justin123/graph1)
2. [Graph -- Shortest path algorithm](https://hackmd.io/@Justin123/graph2)
3. [Graph – Spanning Tree](https://hackmd.io/@Justin123/graph3) (You're reading now!)
## Content
1. [Introduction](https://hackmd.io/MeHMqJ8rTou1sMCSzd9bmw?both#Introduction)
2. [Spanning tree](https://hackmd.io/MeHMqJ8rTou1sMCSzd9bmw?both#Spanning-Tree)
3. [Minimum spanning tree (MST)](https://hackmd.io/MeHMqJ8rTou1sMCSzd9bmw?both#Minimum-spanning-tree-MST)
4. [Algorithm for finding MST](https://hackmd.io/MeHMqJ8rTou1sMCSzd9bmw?both#Algorithm-for-finding-the-MST)
5. [Summary](https://hackmd.io/MeHMqJ8rTou1sMCSzd9bmw?both#Summary)
6. [Reference](https://hackmd.io/MeHMqJ8rTou1sMCSzd9bmw?both#Reference)
## Introduction
Last time, we talked about how to find shortest path. Today, we're going to discuss a similar issue -- find the minimun spanning tree.
## Spanning Tree
Given an undirected graph and using **|V| - 1 edges** to connect all the vertex, the result graph is spanning tree. ==Tree is a graph without loop inside==. Therefore, the spanning tree is a graph connect all the vertex without any loop in it.
```graphviz
graph test {
// title
labelloc="t";
label = "Original graph\n\n";
rankdir=LR;
A -- B [label = "2"]
B -- C [label = "5"]
A -- C [label = "3"]
C -- D [label = "9"]
B -- D [label = "1"]
B -- E [label = "10"]
D -- E [label = "3"]
}
```
```graphviz
graph test {
// title
labelloc="t";
label = "Spanning tree\n\n";
rankdir=LR;
A -- B [label = "2"]
B -- C [label = "5"]
C -- D [label = "9"]
D -- E [label = "3"]
}
```
## Minimum spanning tree (MST)
If the graph possesses different weights, there exists at least **minimun spanning tree**. Here is some application of minimun spanning tree.
* **Connect all villages**
Suppose we have **A**, **B**, **C**, **D** and **E** villages. We want to find minimum cost to build the road from one village to another and each village should has a path to go to other village.
```graphviz
graph test {
// title
labelloc="t";
label = "Cost for building the roads\n\n";
rankdir=LR;
A -- B [label = "2"]
B -- C [label = "5"]
A -- C [label = "3"]
C -- D [label = "9"]
B -- D [label = "1"]
B -- E [label = "10"]
D -- E [label = "3"]
}
```
Within the graph above, we know the minimun spanning tree is:
```graphviz
graph test {
// title
labelloc="t";
label = "Minimum cost for building the roads\n\n";
rankdir=LR;
A -- B [label = "2"]
B -- D [label = "1"]
D -- E [label = "3"]
A -- C [label= "3"]
}
```
Here is the constraints for finding MST:
1. We must use only edges **within the graph**.
2. We must use exactly **|V| - 1** edges.
3. We may **not use edges that produce a cycle**.
## Algorithm for finding the MST
* **Prim**
The idea in **Prim algorithm** is to use the **minimum the weight** to connect two **MST**. This seems to be too abstract to image. Let's see an example.
```graphviz
graph test {
// title
labelloc="t";
label = "Two MST\n\n";
rankdir=LR;
B -- D [label = "1"]
D -- E [label = "3"]
A -- C [label = "3"]
}
```
If we want to find the MST of these nodes, we only have to connect the **minimum edge** from MST1 to MST2, namely, the edge from **A to B**. Therefore, the whole BST will be
```graphviz
graph test {
// title
labelloc="t";
label = "MST for whole tree\n\n";
rankdir=LR;
A -- C [label = "3"]
B -- D [label = "1"]
D -- E [label = "3"]
A -- B [label = "2"]
}
```
Let's define **$V$** to be the set of all the vertex, **$X$** to be the set of all the MST we have now, **$V - X$** be the set of all the vertex not in **$X$**. Now, we only have to start from one node, A, and we can find the MST of the whole graph.
A is now the only element in set **$X$** and all the other vertex is in $V-X$.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 1\n\n";
rankdir=LR;
B -- C [label = "5"]
C -- D [label = "9"]
B -- D [label = "1"]
B -- E [label = "10"]
D -- E [label = "3"]
A [color="red"]
}
```
The min edges from **$X$** to **$V - X$** is 2, then connect it and put **$B$** into **$X$** and remove **$B$** from **$V - X$**.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 2\n\n";
rankdir=LR;
A -- B [label = "2"]
C -- D [label = "9"]
D -- E [label = "3"]
A, B [color = "red"]
}
```
The min edges from **$X$** to **$V - X$** is **$1$**, then connect it and put **D** into $X$ and remove **D** from **$V - X$**.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 3\n\n";
rankdir=LR;
E
A -- B [label = "2"]
B -- D [label = "1"]
C
A, B, D[color = "red"]
}
```
$weight(A, C)$ and $weight(D, E)$ are both the minimum edges from **$X$** to **$V - X$**, then pick whichever we want.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 4\n\n";
rankdir=LR;
E
A -- B [label = "2"]
B -- D [label = "1"]
A -- C [label = "3"]
A, B, C, D[color = "red"]
}
```
Final step.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 5\n\n";
rankdir=LR;
D -- E [label = "3"]
A -- B [label = "2"]
B -- D [label = "1"]
A -- C [label = "3"]
A, B, C, D, E[color = "red"]
}
```
Now, we find the MST of the graph.
```cpp=
// Adjacent matrix
int cost[number_of_vertex][number_of_vertex];
// The minimun weight in set X
int mincost[number_of_vertex];
// Check whether vertex is in tree
bool used[number_of_vertex]
int prim() {
// Init the distance and flag
fill(mincost, mincost + number_of_vertex, INF_MAX);
fill(used, used + number_of_vertex, false);
// Set the first cost to 0
mincost[0] = 0;
// Result for the MST
int res = 0;
while(true) {
// The vertex going to check
int start = -1;
// Get the node from set V - X
for (int i = 0; i < number_of_vertex; ++i) {
if (!used[i] &&
(start == -1 || mincost[i] < mincost[start])) {
start = i;
}
}
// Finish building MST
if (start == -1) break;
// Add start to set X and add the cost to res
used[start] = true;
res += mincost[start];
// Update the mincost to set V - X
for (int i = 0; i < number_of_vertex; ++i) {
mincost[i] = min(mincost[i], cost[start][i]);
}
}
return res;
}
```
---
* **Kruskal**
The approach that Kruskal adopted was:
1. Everytime find the **minimum edges** in the tree.
2. Check whether new edge will form the loop
3. If it does, drop it. Otherwise, **add it to set $X$**. Remove the edge from the container.
4. Back to step 1 </br></br>
For example:
```graphviz
graph test {
// title
labelloc="t";
label = "Example\n\n";
rankdir=LR;
A -- B [label = "2"]
B -- C [label = "5"]
A -- C [label = "3"]
C -- D [label = "9"]
B -- D [label = "1"]
B -- E [label = "10"]
D -- E [label = "3"]
}
```
So the edge container should be:
```graphviz
graph g {
node[shape = record fontsize=15];
rankdir=LR;
a [label = "1\nB\-D"]
b [label = "2\nA\-B"]
c [label = "3\nA\-C"]
d [label = "3\nD\-E"]
e [label = "5\nB\-C"]
f [label = "9\nC\-D"]
g [label = "10\nB\-E"]
a -- b
b -- c
c -- d
d -- e
e -- f
f -- g
}
```
First pick up $edge(B, D)$.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 1\n\n";
rankdir=LR;
B -- D [label = "1"]
}
```
```graphviz
graph g {
node[shape = record fontsize=15];
rankdir=LR;
b [label = "2\nA\-B"]
c [label = "3\nA\-C"]
d [label = "3\nD\-E"]
e [label = "5\nB\-C"]
f [label = "9\nC\-D"]
g [label = "10\nB\-E"]
b -- c
c -- d
d -- e
e -- f
f -- g
}
```
Pick $edge(A, B)$.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 2\n\n";
rankdir=LR;
A -- B [label = "2"]
B -- D [label = "1"]
}
```
```graphviz
graph g {
node[shape = record fontsize=15];
rankdir=LR;
c [label = "3\nA\-C"]
d [label = "3\nD\-E"]
e [label = "5\nB\-C"]
f [label = "9\nC\-D"]
g [label = "10\nB\-E"]
c -- d
d -- e
e -- f
f -- g
}
```
Pick $edge(A, C)$.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 3\n\n";
rankdir=LR;
A -- B [label = "2"]
A -- C [label = "3"]
B -- D [label = "1"]
}
```
```graphviz
graph g {
node[shape = record fontsize=15];
rankdir=LR;
d [label = "3\nD\-E"]
e [label = "5\nB\-C"]
f [label = "9\nC\-D"]
g [label = "10\nB\-E"]
d -- e
e -- f
f -- g
}
```
Pick $edge(D, E)$
```graphviz
graph test {
// title
labelloc="t";
label = "Step 4\n\n";
rankdir=LR;
A -- B [label = "2"]
A -- C [label = "3"]
B -- D [label = "1"]
D -- E [label = "3"]
}
```
```graphviz
graph g {
node[shape = record fontsize=15];
rankdir=LR;
e [label = "5\nB\-C"]
f [label = "9\nC\-D"]
g [label = "10\nB\-E"]
e -- f
f -- g
}
```
Pick $edge(B, C)$, but it will form the loop, then drop it.
```graphviz
graph test {
// title
labelloc="t";
label = "Step 5\n\n";
rankdir=LR;
A -- B [label = "2"]
A -- C [label = "3"]
B -- D [label = "1"]
D -- E [label = "3"]
}
```
```graphviz
graph g {
node[shape = record fontsize=15];
rankdir=LR;
f [label = "9\nC\-D"]
g [label = "10\nB\-E"]
f -- g
}
```
For both $edge(C, D)$ and $edge(B, E)$ form the loop, then drop them both. The tree here is MST.
```graphviz
graph test {
// title
labelloc="t";
label = "MST\n\n";
rankdir=LR;
A -- B [label = "2"]
A -- C [label = "3"]
B -- D [label = "1"]
D -- E [label = "3"]
}
```
```cpp=
class Union {
public:
Union(int number_of_vertices) {
parent = new int[number_of_vertices];
rank = new int[number_of_vertices];
// Init the structure
for (int i = 0; i < number_of_vertices; ++i) {
parent[i] = -1;
rank[i] = 0;
}
}
~Union() {
delete[] parent;
delete[] rank;
}
int find(int x) {
// If parent equal itself, then return it
if (parent[x] < 0) {
return x;
}
else { // return the find(parent[x])
return find(parent[x])
}
}
void unite(int x, int y) {
// First find the tree root
x = find(x);
y = find(y);
if (x == y) { // No need to update
return ;
}
if (rank[x] < rank[y]) { // Add small rank to big rank
parent[x] = y;
}
else {
parent[y] = x;
// increase 1 if rank are the same
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}
bool same(int x, int y) {
// If the parent are the same return true, else return false
return find(x) == find(y);
}
private:
int* parent;
int* rank;
}
```
```cpp=
// Struct for the edges
struct edge {
int u, v cost;
}
// For finding the parent
int parent[number_of_vertices];
// For finding the rank of the tree
int rank[number_of_vertices];
// Container for saving the edges
edge es[number_of_edges];
// Key function for sorting
bool comp(const edge& e1, const edge& e2) {
return e1.cost < e2.cost;
}
int Kruskal() {
// First sort the edges by their weights
sort(es, es + number_of_edges, comp);
// Form the union find
uni = Union(number_of_vertices);
// Init the result to 0
int res = 0;
// Start find the edges
for (int i = 0; i < number_of_edges; ++i) {
// Pop out the first edges
edge e = es[i];
// If won't form the circle
if (!uni.same(e.u, e.v)) {
// then unite them
uni.unite(e.u, e.v);
res += e.cost;
}
}
// return the result
return res;
}
```
## Summary
In this session, we discuss what is spanning tree and how to find the minumum spanning tree. These three articles are all about graph. Thanks for reading!
## Reference
1. [培養與鍛鍊程式設計的邏輯腦 第二版](https://www.books.com.tw/products/0010616945?gclid=Cj0KCQjwoub3BRC6ARIsABGhnyamNtOnA0U1z3yzZeFonqM2HT7jnj1WZcRX8ArR1_KwV3YEgkkkPlIaAlCZEALw_wcB)
Google Drive
Gist
Clipboard
Sign in with Wallet
