最小生成树算法：Kruskal 与 Prim算法

利刃大大

发布于 2023-04-12 14:26:02

1.9K0

发布于 2023-04-12 14:26:02

文章被收录于专栏：编程语言/linux/算法编程语言/linux/算法

Ⅰ. 最小生成树

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。

若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边。因此构造最小生成树的准则有三条：

只能使用图中的边来构造最小生成树
只能使用恰好 n-1 条边来连接图中的 n 个顶点
选用的 n-1 条边不能构成回路

构造最小生成树的方法：Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的贪心策略。

贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择，而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解（也就是说这两种算法不是万能的）。

🔴 并且 最小生成树是不唯一的！

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9WuacIsM-1671589208764)(../../img/image-20221117143459280.png)]

Ⅱ、Kruskal算法

任给一个有 n 个顶点的连通网络 N={V,E}，

首先构造一个由这 n 个顶点组成、不含任何边的图 G={V,NULL}，其中每个顶点自成一个连通分量，

其次不断从 E 中取出权值最小的一条边 ( 若有多条任取其一 ) ，若该边的两个顶点来自不同的连通分量，则将此边加入到 G 中。

如此重复，直到所有顶点在同一个连通分量上为止。

核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4w83JHVr-1671589208765)(../../img/image-20221117143915810.png)]

具体实现的时候，由于考虑到每次都要选最小的一条边，那这里就用 优先级队列，也就是一个堆，来进行存放，并且是一个小堆，每次堆顶是最小的边！一般来说我们操作的一般是无向图，所以只需要将矩阵中的上三角行列式中的边入队列即可~

除此之外，还要 判断连接起来的边会不会形成环路，这个时候我们就可以用 并查集 来判断，每次将选择的边对应的邻接顶点加入到并查集中，然后每次新增边的时候 判断一下新增的边引入的邻接顶点是否已经在并查集中，是的话说明形成回路了，则不选这条边~ （ 🦅 并查集的具体实现翻笔记查找）

另外我们还需要单独 弄个结构体包装一下边的属性：

// 为下面一些算法如Kruskal算法做准备的
struct Edge
{
    size_t _srci;
    size_t _dsti;
    W _weight;

    Edge(size_t srci, size_t dsti, const W& weight)
        :_srci(srci)
        , _dsti(dsti)
        , _weight(weight)
    {}

    // 下面要比较边的大小，所以要重载一下比较
    bool operator>(const Edge& e) const
    {
        return _weight > e._weight;
    }
};

// 下面Kruskal算法接收的参数需要用到默认构造函数
Graph() = default;

typedef Graph<V, W, MAX_W, Direction> Self;

// Kruskal算法
// 下面的minTree是接收的一般是未初始化的图，所以我们要有默认的构造函数
W Kruskal(Self& minTree)
{
    // 初始化一下最小生成树的模板
    size_t n = _vertexs.size();
    minTree._vIndexMap = _vIndexMap;
    minTree._vertexs = _vertexs;
    minTree._matrix.resize(n);
    for (size_t i = 0; i < n; ++i)
    {
        // 默认这些顶点都是不相通的
        minTree._matrix[i].resize(n, MAX_W);
    }

    // 由于我们要从小到大排序，所以得传仿函数过去
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

    // 将矩阵中的边入队列
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < n; ++j)
        {
            // 由于是无向图，我们只需要将上三角行列式中的边加入即可
            if (i < j && _matrix[i][j] != MAX_W)
            {
                pq.push(Edge(i, j, _matrix[i][j]));
            }
        }
    }

    // 贪心算法，从最小的边开始选
    int size = 0;    // 选出n-1条边，所以用size来计数
    W sum = W();     // 最后结束的时候返回最小生成树的总权值
    UnionFindSet ufs(n);    // 并查集

    while (!pq.empty())
    {
        Edge min = pq.top();
        pq.pop();

        // 判断是否成环
        if (!ufs.IsInSameSet(min._srci, min._dsti))
        {
            cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;

            // 将边加上去（注意这里调用的是_AddEdge，接收的参数是下标而不是顶点的版本）
            minTree._AddEdge(min._srci, min._dsti, min._weight);

            // 再将两个点算入并查集
            ufs.Union(min._srci, min._dsti);

            sum += min._weight;
            ++size;
        }
        else
        {
            cout << "构成环： ";
            cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;
        }
    }

    // 若成功生成最小生成树则返回sum，否则返回默认值
    if (size == n - 1)
        return sum;
    else
        return W();
}

我们还要对 AddEdge 函数修改一下，因为我们在 Kruskal 算法中传过去的是下标，但是我们之前的 AddEdge 接收的是顶点，所以我们稍微修改一下~

// 下面函数的子函数，这个接收的参数是下标，这是为了给下面的算法用的
void _AddEdge(size_t srci, size_t dsti, const W& w)
{
    _matrix[srci][dsti] = w;
    // 判断是否为无向图，是的话矩阵要对称赋值
    if (Direction == false)
    {
        _matrix[dsti][srci] = w;
    }
}

// 链接边的函数，接收的参数是顶点
void AddEdge(const V& src, const V& dst, const W& w)
{
    size_t srci = GetVertexIndex(src);
    size_t dsti = GetVertexIndex(dst);

    _AddEdge(srci, dsti, w);
}

下面实现中的测试样例如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pC4P5Eyh-1671589208765)(../../img/image-20221117160441151.png)]

void TestGraphMinTree()
{
    const char* str = "abcdefghi";
    Graph<char, int> g(str, strlen(str));
    g.AddEdge('a', 'b', 4);
    g.AddEdge('a', 'h', 8);
    g.AddEdge('a', 'h', 9);
    g.AddEdge('b', 'c', 8);
    g.AddEdge('b', 'h', 11);
    g.AddEdge('c', 'i', 2);
    g.AddEdge('c', 'f', 4);
    g.AddEdge('c', 'd', 7);
    g.AddEdge('d', 'f', 14);
    g.AddEdge('d', 'e', 9);
    g.AddEdge('e', 'f', 10);
    g.AddEdge('f', 'g', 2);
    g.AddEdge('g', 'h', 1);
    g.AddEdge('g', 'i', 6);
    g.AddEdge('h', 'i', 7);

    Graph<char, int> kminTree;
    cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
    kminTree.Print();
}

// 运行结果----------------------------------------------------------------------
g->h:1
c->i:2
f->g:2
c->f:4
a->b:4
构成环： g->i:6
构成环： h->i:7
c->d:7
b->c:8
构成环： a->h:9
d->e:9
构成环： e->f:10
构成环： b->h:11
构成环： d->f:14
Kruskal:37
[0]->a
[1]->b
[2]->c
[3]->d
[4]->e
[5]->f
[6]->g
[7]->h
[8]->i

     0   1   2   3   4   5   6   7   8
0    *   4   *   *   *   *   *   *   *
1    4   *   8   *   *   *   *   *   *
2    *   8   *   7   *   4   *   *   2
3    *   *   7   *   9   *   *   *   *
4    *   *   *   9   *   *   *   *   *
5    *   *   4   *   *   *   2   *   *
6    *   *   *   *   *   2   *   1   *
7    *   *   *   *   *   *   1   *   *
8    *   *   2   *   *   *   *   *   *

Ⅲ、Prim算法

除了 Kruskal 算法以外，普里姆算法（Prim 算法）也是常用的最小生成树算法。虽然在效率上差不多。但是贪心的方式和 Kruskal 完全不同。prim 算法的核心信仰是：从已知扩散寻找最小。它的实现方式和 Dijkstra算法相似但稍微有所区别，Dijkstra 是求单源最短路径。而每计算一个点需要对这个点从新更新距离。而 prim 甚至不用更新距离。直接找已知点的邻边最小加入即可！

Prim算法原理：

以某一个点开始，寻找当前该点可以访问的所有的边；
在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
寻找当前集合可以访问的所有边，重复步骤2的过程，直到没有新的点可以加入；
此时由所有边构成的树即为最小生成树。

在实现过程中，考虑到每次要挑选已有点的边的最小权值问题，所以我们还是得用**优先级队列，效率会比较高一些！但是要注意的是，我们不能一开始就将所有的边入队列，因为 Prim 算法是通过顶点来找边的，只能找已经确认的点的邻接边，所以我们只能边走边将邻接边入队列**！

除此之外，我们还 需要判断一下加入的边会不会构成环，考虑到 Prim 算法与 Kruskal 算法不同的点也在于 Prim 算法是以点为对象的，所以我们时时刻刻都知道哪些点是已经确定的，所以我们可以用一个 vector<bool> 来标记这些顶点，true 表示这些顶点在这个集合，false 表示这些顶点不在！（当然也可以用两个 set ，一个 set 存储已经存在的顶点，另一个 set 存储还没有确认的顶点，然后分别去查找、插入、删除。但是显然没有我们用 vector 快，所以这里我们选用 vector！）

// Prim算法
// minTree是接收的未初始化的图，所以我们要有默认的构造函数
// src是首个顶点
W Prim(Self& minTree, const V& src)
{
    size_t srci = GetVertexIndex(src);

    // 初始化图，与Kruskal算法一样
    size_t n = _vertexs.size();
    minTree._vertexs = _vertexs;
    minTree._vIndexMap = _vIndexMap;
    minTree._matrix.resize(n);
    for (size_t i = 0; i < n; ++i)
        minTree._matrix[i].resize(n, MAX_W);

    // 使用vector来存储顶点的确认情况：是否在生成树中已经确认（默认是不确认）
    // true表示确认存在
    // false表示还不确认存在
    vector<bool> vState(n, false);
    vState[srci] = true;    // 注意将首个顶点设置为true

    // 初始化优先级队列（与Kruskal算法一样）
    // 先将与首个顶点邻接的边入队列
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    for (size_t i = 0; i < n; ++i)
    {
        if (_matrix[srci][i] != MAX_W)
            pq.push(Edge(srci, i, _matrix[srci][i]));
    }

    size_t size = 0;
    W sum = W();
    cout << "Prim开始选边" << endl;
    while (!pq.empty())
    {
        Edge min = pq.top();
        pq.pop();

        // 判断一下是否成环
        // 若这条边的目标节点下标是已经确认的，说明是成环的，反之不成环
        if (vState[min._dsti] == true)
        {
            cout << "构成环：";
            cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;
        }
        else
        {
            cout << minTree._vertexs[min._srci] << "->" <<minTree._vertexs[min._dsti] << ":" << min._weight << endl;

            // 将边添加到生成树中去	
            minTree._AddEdge(min._srci, min._dsti, min._weight);
            vState[min._dsti] = true;  // 将目的顶点设为确认
            sum += min._weight;
            size++;

            if (size == n - 1)
                break;

            // 将目的顶点的邻接边入队列，继续循环
            for (size_t i = 0; i < n; ++i)
            {
                // 若它的邻接边是存在的且该目的顶点还未被确认，则入队列
                if (_matrix[min._dsti][i] != MAX_W && vState[i] == false)
                    pq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
            }
        }
    }

    // 若成功生成最小生成树则返回sum，否则返回默认值
    if (size == n - 1)
        return sum;
    else
        return W();
}

下面实现中的测试样例如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kJjqBEhl-1671589208765)(…/…/img/image-20221118151918165.png)]

void TestGraphMinTree()
{
    const char* str = "abcdefghi";
    Graph<char, int> g(str, strlen(str));
    g.AddEdge('a', 'b', 4);
    g.AddEdge('a', 'h', 8);
    //g.AddEdge('a', 'h', 9);
    g.AddEdge('b', 'c', 8);
    g.AddEdge('b', 'h', 11);
    g.AddEdge('c', 'i', 2);
    g.AddEdge('c', 'f', 4);
    g.AddEdge('c', 'd', 7);
    g.AddEdge('d', 'f', 14);
    g.AddEdge('d', 'e', 9);
    g.AddEdge('e', 'f', 10);
    g.AddEdge('f', 'g', 2);
    g.AddEdge('g', 'h', 1);
    g.AddEdge('g', 'i', 6);
    g.AddEdge('h', 'i', 7);

    Graph<char, int> pminTree;
    cout << "Prim:" << g.Prim(pminTree, 'a') << endl << endl;
    pminTree.Print();
}

// 运行结果
Prim开始选边
a->b:4
a->h:8
h->g:1
g->f:2
f->c:4
c->i:2
构成环：g->i:6
c->d:7
构成环：h->i:7
构成环：b->c:8
d->e:9
Prim:37
    
[0]->a
[1]->b
[2]->c
[3]->d
[4]->e
[5]->f
[6]->g
[7]->h
[8]->i

     0   1   2   3   4   5   6   7   8
0    *   4   *   *   *   *   *   8   *
1    4   *   *   *   *   *   *   *   *
2    *   *   *   7   *   4   *   *   2
3    *   *   7   *   9   *   *   *   *
4    *   *   *   9   *   *   *   *   *
5    *   *   4   *   *   *   2   *   *
6    *   *   *   *   *   2   *   1   *
7    8   *   *   *   *   *   1   *   *
8    *   *   2   *   *   *   *   *   *