6.4 最小代价生成树

  • 一棵带权无向图的生成树的 「代价 cost」 是该生成树中所有边的代价(权值)之和。「最小代价生成树 minimum cost spanning tree」 就是一棵代价最小的生成树。可以采用三种不同的算法获得连通无向图的最小代价生成树。这三个算法分别是 「Kruskal 算法」「Prim 算法」「Sollin 算法」。这三种算法采用的算法设计策略都是 「贪心法 greedy method」
  • 对于最小生成树问题,使用最小代价判断标准。问题的解必须满足下列约束条件:

    1. 只能使用图中的边;
    2. 只能使用恰好 n1n - 1 条边;
    3. 不能使用产生环路的边。
  • 「Kruskal 算法」 通过每次向当前最小代价生成树 TT 中加入一条边的方法构造最终的最小生成树 TT。算法按照边的代价递增选取,并加入 TT 中。如果所选取的边与 TT 中的边不形成环路,则这条边加入到 TT 中。由于图 GG 是连通的,且具有 nn 个顶点 (n>0)(n>0),所以最终恰好选取 n1n - 1 条边加入到 TT 中。

T = {};
while (T.count < n-1 && E 不为空)
{
    从 E 中选取代价最低的边 (v, w);
    在 E 中删除边 (v, w);
    if ((v, w) 在 T 中不会形成一个环形)
        add (v, w) to T;
    else
        discard (v, w);
    if (T 包含少于 n-1 条边)
        无生成树;
}

如下图,算法找到的权值依次增加的边分别为 (0,5),(2,3),(1,6),(1,2),(3,6),(3,4),(4,6),(4,5),(0,1)(0, 5), (2, 3), (1, 6), (1, 2), (3, 6), (3, 4), (4, 6), (4, 5), (0, 1),将它们依次加入树,而边 (3,6),(4,6),(0,1)(3, 6), (4, 6), (0, 1) 会与其之前加入的边形成环路,因此将这三条边舍弃。最终得到下图右边的最小代价生成树。

6-17

「Kruskal 算法」使用最小堆来实现找出下一个最小权值的边,最小堆可以在 O(loge)O(\log e) 时间内找出并删除下一条最小权值的边。而构造最小堆的时间复杂度为 O(e)O(e),为了检查新边 (v,w)(v, w) 加入 TT 后不产生环路,可以使用 5.10 集合表示 中的 union-find 算法,TT 中所有连通的顶点都在同一个集合中,检查 vvww 是否在同一个集合中这一操作的时间开销的时间开销小,因此整个算法的时间复杂度为 O(eloge)O(e\log e)

  • 「Prim 算法」 从只包含一个顶点的树 TT 开始,该顶点可以是原图中的任意一个顶点。然后,把一条代价最小的边 (u,v)(u, v) 加入 TT 中,使 T{(u,v)}T \cup \{(u, v)\} 仍是一棵树。重复上述加入过程直到 TT 中包含 n1n - 1 条边为止。为了保证所加入的边不形成环路,要求在每一步所选取的边 (u,v)(u, v) 的两个顶点 uuvv,只能有一个顶点在 TT 中。如下伪代码,T 是生成树中的边集,TV 是当前生成树 TT 的顶点集合。「Prim 算法」的时间复杂度为 O(n2)O(n^2)
T = {};
TV = {0}; // 从顶点 0 开始
while (T 包含少于 n-1 条边)
{
    使 (u, v) 是权值最小的边,其中 u ∈ TV, v ∉ TV;
    if (边 (u, v) 不存在)
        break;
    add v to TV;
    add (u, v) to T;
}
if (T 包含少于 n-1 条边)
    无生成树;

6-18

  • 「Sollin 算法」 步骤如下:

    1. 令图中每个顶点表示一棵树,原图构成一个森林 TT
    2. TT 中每棵树选择一个最小代价边,使得加入后仍是一棵树;
    3. 重复 2,直到 TT 中只有一棵树。

    如下图,为顶点 0,1,2,3,4,5,60, 1, 2, 3, 4, 5, 6 选取边,分别为 (0,5),(1,6),(2,3),(3,2),(4,3),(5,0),(6,1)(0, 5), (1, 6), (2, 3), (3, 2), (4, 3), (5, 0), (6, 1),去掉重复的边后,剩下的边是:(0,5),(1,6),(2,3),(4,3)(0, 5), (1, 6), (2, 3), (4, 3)。接下来,为树 {0,5}\{0, 5\} 选取边 (5,4)(5, 4),而为剩下两棵树选取边 (1,2)(1, 2)

6-19

results matching ""

    No results matching ""