---
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.

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"]
}

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.

    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:

    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.

    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

    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$.

    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$**.

    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$**.

    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.

    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.

    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.

    // 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:

    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:

    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)$.

    graph test {
        // title
        labelloc="t";
        label = "Step 1\n\n";

        rankdir=LR;
        B -- D [label = "1"]
    
    }

    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)$.

    graph test {
        // title
        labelloc="t";
        label = "Step 2\n\n";

        rankdir=LR;
        A -- B [label = "2"]
        B -- D [label = "1"]
    
    }
    

    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)$.

    graph test {
        // title
        labelloc="t";
        label = "Step 3\n\n";

        rankdir=LR;
        A -- B [label = "2"]
        A -- C [label = "3"]
        B -- D [label = "1"]
    
    }
    

    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)$

    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"]
    
    }
    

    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.

    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"]
    
    }
    

    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.

    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"]
    
    }
    

    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;
    }

    // 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)