Graph – Spanning Tree

Relative articles

Graph – Basic concept
Graph – Shortest path algorithm
Graph – Spanning Tree (You're reading now!)

Content

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.

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.

Within the graph above, we know the minimun spanning tree is:

Here is the constraints for finding MST:

We must use only edges within the graph.
We must use exactly |V| - 1 edges.
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.

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

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

The min edges from

$X$ to
$V - X$ is 2, then connect it and put
$B$ into
$X$ and remove
$B$ from
$V - X$ .

The min edges from

$X$ to
$V - X$ is
$1$ , then connect it and put D into

X

and remove D from
$V - X$ .

w e i g h t (A, C)

and

w e i g h t (D, E)

are both the minimum edges from
$X$ to
$V - X$ , then pick whichever we want.

Final step.

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:

Everytime find the minimum edges in the tree.
Check whether new edge will form the loop
If it does, drop it. Otherwise, add it to set
$X$ . Remove the edge from the container.
Back to step 1

For example:

So the edge container should be:

First pick up

e d g e (B, D)

Pick

e d g e (A, B)

Pick

e d g e (A, C)

Pick

e d g e (D, E)

Pick

e d g e (B, C)

, but it will form the loop, then drop it.

For both

e d g e (C, D)

and

e d g e (B, E)

form the loop, then drop them both. The tree here is MST.



























































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

培養與鍛鍊程式設計的邏輯腦第二版

Graph – Spanning Tree

Relative articles

Content

Introduction

Spanning Tree

Minimum spanning tree (MST)

Algorithm for finding the MST

Summary

Reference

Read more

Graph -- Basic concept

Graph -- Shortest path algorithm

OpenCV series

OpenCV with Python -- 4