最小支撑树

支撑树

连通图G的某一无环连通子图T若覆盖G中所有的顶点，则称作G的一棵支撑树或生成树

支撑树.png

最小支撑树

若图G为一带权网络，则每一颗支撑树的成本则为其所采用各边权重的总和。在所有的支撑树中，成本最低者称作最小支撑树。

蛮力法

逐一考查G的所有支撑树并统计其成本，从而挑选出其中最低者。然而由n个互异顶点组成的完全图一共有n^(n-2)棵支撑树。

Prim算法

图G = （V， E）中，定点集V的任一非平凡子集U及其补集V \ U都构成G的一个割(cut)，记作（U：V \ U），
若边uv满足u∈U，且v∉ U, 则称作该割的一条跨越边。

Prim算法正确性基于以下事实：最小支撑树总是采用联接每一割的最短跨越边。

大致思想是：
首先从图的顶点V中的一点作为起始点a，将该点加入集合U，再从集合V\U中找到另一点b，使得点b到V中任意一点的权值最小，此时将b点加入集合U中。以此类推：现在的集合V={a, b}，再从集合V \ U中找到点c，使得点c到V中任意一点的权值最小，此时将c加入集合V中。这样下去，直到所有顶点都被加入到V。此时就构建除了一棵最小支撑树。

void Prim()
{
    while(true) {
        if (未收录顶点集合为空)
             break;
        V = 未收录顶点集合中dist最小的顶点  /*dist 记录顶点被纳入生成树时的边的权值*/
         for (V 的每个邻接点W)
             if (W未被收录)
                 if ( E(V, W) < dist[W]) {
                     dist[W] = E[V, W];
                     parent[W] = V; 
                 }
    }
}

1 2.png 3.png

void Graph::prim(int s) {
    std::vector<int> notIncluded;   // 未被收录的顶点
    for (int i = 0; i != n; i++)    // 初始化时，所有顶点都未被收录
        notIncluded.push_back(i);
    
    /* 初始化顶点在被加入最小生成树时距离最小生成树的距离(边权值) */
    dist.resize(n);
    for (int i = 0; i < n; i++)
        dist[i] = (i == s ? 0 : INT_MAX);

    /* 初始化记录生成树顶点遍历路径的parent数组 */
    parent.resize(n, -1);

    while(true) {
        if (notIncluded.empty())
            break;

        /* 从未被收录顶点集合中找出一个dist值最小的顶点 */
        int v = [&notIncluded, this]() -> int {
            int min = notIncluded[0];
            for (const auto &i : notIncluded)
                if (dist[i] < this->dist[min])
                    min = i;
            return min;
        }();

        auto iter = find(notIncluded.begin(), notIncluded.end(), v);
        notIncluded.erase(iter);

        for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
            if (find(notIncluded.begin(), notIncluded.end(), u) != notIncluded.end()) {
                if (weight(v, u) < dist[u]) {
                    dist[u] = weight(v, u);
                    parent[u] = v;
                }
            }
        }
    }
}

Kruskal算法

• 基本思路
  • 首先将G的n个顶点看成n个孤立的连通分支(n个孤立点)
  • 按照边权递增顺序，如果加入该边后形成环路，则不加这条边，直到形成最小支撑树。

void Kruskal(Graph G) {
    MST = {  };
    while( MST中不到|V|-1条边 && E中还有边)
        从E中取出一条权重最小的边e<v, w>;  /* 最小堆*/
        将e<v, w>从E中删除
        if ( E<V, M>不在MST中构成回路)    /* 并查集 */
            将e<v, w>加入MST;
}

Kruskal算法.png