Minimum Spanning Trees

2018/08/10 ALGO

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

Assumptions

An edge-weighted graph is a graph where we associate weights or costs with each edge. A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.

To streamline the presentation, we adopt the following conventions:

  1. The graph is connected. The spanning-tree condition in our definition implies that the graph must be connected for an MST to exist. If a graph is not connected, we can adapt our algorithms to compute the MSTs of each of its connected components, collectively known as a minimum spanning forest.
  2. The edge weights are not necessarily distances. Geometric intuition is sometimes beneficial, but the edge weights can be arbitrary.
  3. The edge weights may be zero or negative. If the edge weights are all positive, it suffices to define the MST as the subgraph with minimal total weight that connects all the vertices.
  4. The edge weights are all different. If edges can have equal weights, the minimum spanning tree may not be unique. Making this assumption simplifies some of our proofs, but all of our our algorithms work properly even in the presence of equal weights.

Underlying principles

We recall two of the defining properties of a tree:

  1. Adding an edge that connects two vertices in a tree creates a unique cycle.
  2. Removing an edge from a tree breaks it into two separate subtrees.

算法分析

有n个节点的连通图的生成树是原图的极小连通子图,并且有保持图连通的最小的边。通常的有两种古典算法来计算一幅图的最小生成树,分别是Prim以及Kruskal算法。这两种算法从不同的角度出发,但是核心的思路是一致的:贪心算法。下面不给予证明最小生成的正确性,而是描述两种算法的具体操作。

Prim算法

Prim的每一步都会为一棵生长中的树添加1条边,一开始这棵树只有1个顶点,然后会向它添加 V-1 条边(V是节点数量),每次总是将下一条连接树中顶点与不在树中的顶点并且权重最小的边加入树中。

以上图为例:

  1. 一开始这棵树有1个顶点,也即是节点0,有4条边连接着顶点和图。注意,这4条边的特点是,一个端点在树中,另一个端点不在树中。
  2. 紧接着,我们选择0-7这条边加入树中,因为它的权值是4条边中最小的。
  3. 此时树包含了两个点,分别是节点0以及节点7,有7条边连接着树中顶点以及不在树中的顶点(第2幅图的红线)
  4. 紧接着,我们选择1-7这条边加入树中,因为它的权值是7条边中最小的。
  5. 以此类推,直到选择了V-1条边(也就是7条边,最后一幅图的加粗黑色线条)。
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];

// vis数组表示某个节点是否被访问
// lowc数组表示当前树与非树部分的边的权值

int Prim(int cost[][MAXN], int n){
    int ans = 0;
    // memset(vis, false, sizeof(vis));
    vis[0] = true;
    for(int i=1;i<n;i++){
        lowc[i] = cost[0][i];
    }
    for(int i=1;i<n;i++){
        int minc = INF;
        int p = -1;
        for(int j=0;j<n;j++){
            if(!vis[j] && minc > lowc[j]){
                minc = lowc[j];
                p = j;
            }
        }
        // 不存在最小生成树
        if(minc == INF)
            return -1;
        ans += minc;
        vis[p] = true;
        for(int j=0;j<n;j++){
            if(!vis[j] && lowc[j] > cost[p][j]){
                lowc[j] = cost[p][j];
            }
        }
    }
    return ans;
}

Kruskal算法

Kruskal算法的主要思路是按照边的权重排序,将边加入最小生成树中,加入的边不会与已经加入的边构成环,直到树中含有V-1条边为止。这些边逐渐由一片森林合并为一棵树,也就是图的最小生成树。

以上图为例:

  1. 首先我们对所有边按照权值从小到大排序,得到图片右侧的排序结果。
  2. 选择0-7这条边加入生成树中。
  3. 选择2-3这条边加入生成树中。
  4. 选择1-7这条边加入生成树中。
  5. 选择0-2这条边加入生成树中。
  6. 选择5-7这条边加入生成树中。
  7. 选择1-3的时候发现,如果添加1-3这条边,会出现环路,因此不选择。
  8. 以此类推,直到选择了V-1条边(也就是7条边,最后一幅图的加粗黑色线条)。
const int MAXN = 110;
const int MAXM = 10000;
int F[MAXN];

struct Edge{
    int u, v, w;
}edge[MAXM];

// 边的数量,初始为0
int tol;
void addedge(int u, int v, int w){
    edge[tol].u = u;
    edge[tol].v = v;
    edge[tol++].w = w;
}

bool cmp(Edge a, Edge b){
    return a.w < b.w;
}

int find(int x){
    return F[x] == -1 ? x : find(F[x]);
}

int Kruskal(int n){
    memset(F, -1, sizeof(f));
    sort(edge, edge + tol, cmp);
    int cnt = 0;
    int ans = 0;
    for(int i=0;i<tol;i++){
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        int t1 = find(u);
        int t2 = find(v);
        if(t1 != t2){
            ans += w;
            F[t1] = t2;
            cnt++;
        }
        if(cnt == n-1){
            break;
        }
    }
    // 不存在最小生成树
    if(cnt < n-1){
        return -1;
    } else {
        return ans;
    }
}

选用哪个方法更好

这取决于你使用什么数据结构。

例如上面的两份代码中,Prim的代码使用了邻接表来保存一幅图,而Kruskal的代码使用了边的集合,还有一个并查集。如果一幅图是稠密的,那么Prim中的邻接表能够更加饱满,减少数值为null的值(null表示没有边),此时Prim算法在空间上有优势。如果一幅图是稀疏的,也就是边很少的,那么Prim的邻接表就需要占用相比于Kruskal更多的空间,因为存在大量的null,而Kruskal仅仅需要保存边的结构体,因此在空间上有优势。

这两个算法的时间复杂度是一致的,是O(n logn),相对来说,Kruskal会慢一点,因为涉及到并查集的操作。(并查集在这里起到的作用是判断这棵树是否存在环)

拓展

  1. 上述的Prim算法的代码中,可以改用最小优先队列来计算出每一次循环中权值最小的边,以此来提高效率。Kruskal算法呢?它看起来不需要使用最小优先队列,原因是它在最开始已经使用sort函数排序了,后面的算法操作中这个序列不需要更新。

  2. 是否存在线性时间的最小生成树算法呢?目前没有理论证明不存在,但是也没有发现线性时间的MST算法(就好像是外星人一样,没有发现外星人,但是又不能证明不存在)。B.Chazelle的一篇论文中提出了接近线性时间的算法,但是它太复杂了至于难以实用。

  3. 上面的两份代码求解出来的是这棵最小生成树的权值,只需要稍加改进就能计算出这棵树中最长的边或者是最小的边。

  4. 假如有n个节点的无向连通图,那么生成的最小生成树有n-1条边。

Search

    Table of Contents