算法 - 图的实例 - 最小生成树 (Minimum Spanning Tree)

算法 - 图的实例 - 最小生成树 (Minimum Spanning Tree)

返回分类:全部文章 >> 基础知识

返回上级:编程基础 - 图 (Graph)

本文将介绍最小生成树的基础知识,并用C++实现克鲁斯卡尔算法(Kruskal)和普利姆算法(Prim)。

在查看本文之前,需要一些数据结构和程序语言的基础。

尤其是“矩阵”、“矩阵的压缩(matrix)”“图(graph)”“队列(queue)”等的知识。


文章目录


1 最小生成树简述 (Introduction)

  • 对图使用不同的遍历方法,可得到不同的生成树;

  • 从不同的顶点出发也能得到不通过的生成树。

  • 有 n 个顶点的连通且带权的图由 n-1 条边;

  • 最小生成树:

    • 使用 n-1 条边连接网络中的 n 个顶点;
    • 且不能使其产生回路;
    • 各条边的权值总和最小。
  • 重要结论:

    • 当权值各边都不同时,最小生成树一定唯一;
    • 当权值部分相同时:
      • 邻接矩阵:由于选边顺序固定,则最小生成树唯一;
      • 邻接表:由于边链表不唯一,则最小生成树不唯一。

2 克鲁斯卡尔算法 (Kruskal Algorithm)

2.1 算法基本思想 (Basic Idea)

  • (1)构造一个只有原连通带权图顶点的新图,即没有边只有顶点(每个顶点都是一个连通分量);

  • (2)从原连通带权图所有边中选择权值最小的边,如果此边两顶点落在新图中不同的连通分量上,则将此边加入新图,将此边舍去;

  • (3)重复步骤(2),直到所有顶点同时在一个连通分量上。

假设原连通带权图:

25916131122192324ABCDEFG

根据此思想描述生成过程:

Kruskal Step 1 无边新图25916131122192324ABCDEFG Kruskal Step 225916131122192324ABCDEFG Kruskal Step 325916131122192324ABCDEFG Kruskal Step 425916131122192324ABCDEFG Kruskal Step 525916131122192324ABCDEFG Kruskal Step 6 D - G 有回路不能选25916131122192324ABCDEFG Kruskal Step 725916131122192324ABCDEFG Kruskal 最终得到的最小生成树的图25916131122192324ABCDEFG

2.2 算法设计思路 (Design Idea)

  • (1)首先,我们要获取所有的边,还要知道它所连接的顶点,这需要一个数据结构

    // 边
    typedef struct KruskalEdge
    {
        int first;      // 第一个顶点下标
        int second;     // 第二个顶点下标
        double weight;  // 两顶点边的权值
    
        KruskalEdge() : first(-1), second(-1), weight(0.0)
        {
        }
    } PrimEdge;
  • (2)其次,我们需要挑选最小权值的边,这可以使用多种排序方法实现;

  • (3)最后,我们要判断其边两顶点是否在不同的连通分量上 (按图的边) ,这可以使用并查集来实现。

2.3 C++代码 (C++ Code)

  • (1)创建只有顶点的图:

    // Author: https://blog.csdn.net/DarkRabbit
    // Minimum Spanning Tree
    
    // 创建只复制顶点的图
    // params:
    //      graph:      需要复制的图
    AMGraphInt* CreateCopyVertexesGraph(AMGraphInt* graph)
    {
        int size = graph->GetVertexCount(); // 顶点数量
    
        // 获取所有结点值
        std::vector<int> elements = std::vector<int>(size, 0);
        for (int i = 0; i < size; i++)
        {
            graph->TryGetVertex(i, elements[i]);
        }
    
        AMGraphInt* copyGraph = new AMGraphInt(elements, false); // 创建新的无向图
        return copyGraph;
    }
    
  • (2)获取图的所有边,并从小到大排序:

    // Author: https://blog.csdn.net/DarkRabbit
    // Minimum Spanning Tree
    
    // 获取所有边信息
    // params:
    //      graph:      获取边的图
    //      edges:      获取的所有边,并按从小到大排序
    void GetAndSortKruskalEdges(AMGraphInt* graph, std::vector<KruskalEdge>& edges)
    {
        int size = graph->GetVertexCount();
        KruskalEdge edge;
        for (int r = 0; r < size; r++)
        {
            for (int c = 0; c < r; c++) // 无向图,只需下三角
            {
                graph->TryGetWeight(r, c, edge.weight); // 获取权重
                if (edge.weight != graph->GetDefaultWeight()) // 如果两点有边
                {
                    edge.first = r;
                    edge.second = c;
                    edges.push_back(edge);
                }
            }
        }
    
        std::sort(edges.begin(), edges.end(), [](KruskalEdge& lhs, KruskalEdge& rhs)->bool
        {
            return lhs.weight < rhs.weight;
        }); // 从小到大排序
    }
    
  • (3)并查集的查找与并集操作:

    // Author: https://blog.csdn.net/DarkRabbit
    // Minimum Spanning Tree
    
    // 并查集 Find,寻找集合中的根
    // params:
    //      vertexSet:      并查集
    //      val:            查找值
    // return:
    //      int:            返回集合根下标
    int UfsetFind(std::vector<int>& vertexSet, int val)
    {
        while (vertexSet[val] >= 0)
        {
            val = vertexSet[val];
        }
        return val;
    }
    
    // 并查集 Union,合并集合,将元素少的集合合并入元素多的集合
    // params:
    //      vertexSet:      并查集
    //      set1:           集合1
    //      set2:           集合2
    // return:
    //      int:            成为根的集合
    int UfsetUnion(std::vector<int>& vertexSet, int set1, int set2)
    {
        int val = vertexSet[set1] + vertexSet[set2]; // 两个集合元素总数量
        if (vertexSet[set1] > vertexSet[set2])
        {
            vertexSet[set2] = val; // 集合2成为根
            vertexSet[set1] = set2;
            return set2;
        }
        else
        {
            vertexSet[set1] = val; // 集合1成为根
            vertexSet[set2] = set1;
            return set1;
        }
    }
    
  • (4)克鲁斯卡尔算法:

    // Author: https://blog.csdn.net/DarkRabbit
    // Minimum Spanning Tree
    // 克鲁斯卡尔算法
    // params:
    //      graph:                  需要计算的图
    //      paths:                  输出的连接顺序
    // return:
    //      AdjacencyMatrix<int>:   输出的最小生成树的图
    AMGraphInt* Kruskal(AMGraphInt* graph, std::vector<KruskalEdge>& paths)
    {
        if (graph == nullptr || graph->IsOriented()) // 如果是有序图返回
        {
            return nullptr;
        }
    
        AMGraphInt* minTree = CreateCopyVertexesGraph(graph); // 只复制顶点后的图
        int size = minTree->GetVertexCount(); // 顶点数量
        if (size <= 1) // 只有零到一个顶点,直接返回
        {
            return minTree;
        }
    
        std::vector<KruskalEdge> edges; // 边
        GetAndSortKruskalEdges(graph, edges); // 获取所有边,并按从小到大排序
    
        // 初始化并查集,每个结点为一个集合
        std::vector<int> vertexSet = std::vector<int>(size, -1);
    
        // 循环使用并查集加入每一条边
        for (int i = 0; i < edges.size(); i++)
        {
            int set1 = UfsetFind(vertexSet, edges[i].first); // 获取第一个顶点所在集合
            int set2 = UfsetFind(vertexSet, edges[i].second); // 获取第二个顶点所在集合
            if (set1 != set2) // 不在同一集合
            {
                UfsetUnion(vertexSet, set1, set2); // 合并集合
                minTree->TryPutWeight(edges[i].first, edges[i].second, edges[i].weight); // 设置边
                minTree->TryPutWeight(edges[i].second, edges[i].first, edges[i].weight); // 设置边
                paths.push_back(edges[i]);
            }
        }
    
        return minTree;
    }
    

3 普利姆算法 (Prim Algorithm)

2.1 算法基本思想 (Basic Idea)

  • (1)构造一个只有原连通带权图顶点的新图,即没有边只有顶点(每个顶点都是一个连通分量);

  • (2)从顶点中选择一个顶点作为起始连通分量;

  • (3)选择与此连通分量连接的边中权值最小的边,加入连接的顶点且将此边加入到新图中,将此边舍去;

  • (4)重复步骤(3),直到所有顶点同时在一个连通分量上。

假设原连通带权图,起始点为A

25916131122192324ABCDEFG

根据此思想描述生成过程:

Prim Step 1 无边新图25916131122192324ABCDEFG Prim Step 2 A为起始点25916131122192324ABCDEFG Prim Step 3 AF有两条边25916131122192324ABCDEFG Prim Step 4 AFE有3条边25916131122192324ABCDEFG Prim Step 5 AFED有4条边25916131122192324ABCDEFG Prim Step 6 AFEDC有4条边25916131122192324ABCDEFG Prim Step 7 AFEDCB有4条边且AB有回路25916131122192324ABCDEFG Prim 最终得到的最小生成树的图25916131122192324ABCDEFG

2.2 算法设计思路 (Design Idea)

  • (1)首先,我们要获取顶点连接的边,还要知道它所连接的顶点,这需要一个数据结构

    // 边
    typedef struct KruskalEdge
    {
        int first;      // 第一个顶点下标
        int second;     // 第二个顶点下标
        double weight;  // 两顶点边的权值
    
        KruskalEdge() : first(-1), second(-1), weight(0.0)
        {
        }
    } PrimEdge;
  • (2)其次,我们需要挑选最小权值的边,这也可以使用多种排序方法实现;

  • (3)最后,我们要判断其边两顶点是否在不同的连通分量上 (按图的顶点) ,这和广度优先遍历一样,需要访问标记

2.3 C++代码 (C++ Code)

// Author: https://blog.csdn.net/DarkRabbit
// Minimum Spanning Tree
// 普利姆算法
// params:
//      graph:                  需要计算的图
//      begin:                  起始顶点
//      paths:                  输出的连接顺序
// return:
//      AdjacencyMatrix<int>:   输出的最小生成树的图
AMGraphInt* Prim(AMGraphInt* graph, int begin, std::vector<PrimEdge>& paths)
{
    if (graph == nullptr || graph->IsOriented()) // 如果是有序图返回
    {
        return nullptr;
    }

    int size = graph->GetVertexCount(); // 顶点数量
    if (begin < 0 || begin >= size) // 起始点不在图中,直接返回
    {
        return nullptr;
    }

    AMGraphInt* minTree = CreateCopyVertexesGraph(graph); // 只复制顶点后的图
    if (size <= 1) // 只有零到一个顶点
    {
        return minTree;
    }

    std::vector<bool> vertexMark = std::vector<bool>(size, false); // 顶点访问标记
    std::queue<int> vertexes; // 顶点队列
    std::vector<PrimEdge> edges; // 边

    vertexes.push(begin); // 加入起始顶点

    int index; // 当前顶点下标
    while (!vertexes.empty())
    {
        index = vertexes.front();
        vertexes.pop();
        vertexMark[index] = true; // 访问过了

        for (int adj = graph->FirstNeighbor(index);
                adj != -1;
                adj = graph->NextNeighbor(index, adj))
        {
            if (!vertexMark[adj]) // 如果邻接顶点没有找过边
            {
                PrimEdge edge;
                edge.first = index;
                edge.second = adj;
                graph->TryGetWeight(index, adj, edge.weight);
                edges.push_back(edge); // 加入边
            }
        }

        if (!edges.empty())
        {
            std::sort(edges.begin(), edges.end(), [](PrimEdge& lhs, PrimEdge&rhs)->bool
            {
                return lhs.weight < rhs.weight;
            }); // 从小到大

            if (vertexMark[edges[0].second]) // 如果最小权值的边连接的顶点访问过了,证明所有顶点都访问过了
            {
                break;
            }
            else
            {
                minTree->TryPutWeight(edges[0].first, edges[0].second, edges[0].weight); // 设置边
                minTree->TryPutWeight(edges[0].second, edges[0].first, edges[0].weight); // 设置边
                paths.push_back(edges[0]); // 加入输出路径
                vertexes.push(edges[0].second); // 将新连接的顶点加入节点队列
                edges.erase(edges.begin()); // 取出最小边
            }
        }
    }

    return minTree;
}

4 两种算法的比较 (Comparing Two Algorithms)

  • 方式:

    • Kruskal通过边来构造最小生成树;
    • Prim通过顶点来构造最小生成树;
  • 适用范围:

    • Kruskal对边稀疏与边稠密都适用;
    • Prim仅对边稠密适用;
  • 复杂度(n个顶点,e条边,插入删除等使用小根堆O(log2e)):

    • 检测矩阵:邻接矩阵存储O(n2),邻接表O(n±e);
    • Kruskal插入删除e次,则O(e log2e);
    • Prim需要O(n)次循环迭代,每次平均插入2e/n条边,e条边出堆,耗时O(e log2e)。

5 主函数与测试 (Main Method and Testing)

插入,删除与排序,如果不想用内置方法,推荐使用小根堆,即插入:

// Author: https://blog.csdn.net/DarkRabbit
// Minimum Spanning Tree
// 小根堆插入,首下标从1开始
// params:
//      btTree:     堆树
//      val:        插入的值
void BinaryInsertWithOne(std::vector<KruskalEdge>& btTree, KruskalEdge& val)
{
    if (btTree.size() == 0) // 下标从1开始,最少要有一个元素
    {
        btTree.push_back(KruskalEdge());
        btTree.push_back(val);
        return;
    }

    int index = btTree.size(); // 插入后的下标
    btTree.push_back(val); // 插入数值

    int parent = index / 2; // 父结点下标

    while (parent > 0 && btTree[index].weight < btTree[parent].weight) // 如果子结点小
    {
        std::swap(btTree[index], btTree[parent]); // 交换父结点与当前结点
        index = parent; // 重新设定下标
        parent /= 2; // 重新计算父结点
    }
}

5.1 主函数 (Main Method)

// Author: https://blog.csdn.net/DarkRabbit
// Minimum Spanning Tree

#include "abstract_graph.h"
#include "adjacency_matrix.h"

#include "minimum_spanning_tree.h"

#include <vector>
#include <unordered_map>

#include <iomanip>
#include <iostream>
using namespace std;

typedef Graphs::AMVertexNode<int> AMVertexInt;
typedef Graphs::AdjacencyMatrix<int> AMGraphInt;

void TestAdjacencyMatrix();
void TestKruskal();
void TestPrim();

int main()
{
    //TestAdjacencyMatrix();

    TestKruskal();
    TestPrim();

    system("pause");
    return 0;
}

// 打印邻接矩阵
template<class TGraph>
void PrintMatrix(TGraph& graph);

// 克鲁斯卡尔 Kruskal
void TestKruskal()
{
    AMGraphInt* graph = new AMGraphInt({ 0, 1, 2, 3, 4, 5, 6 }, false); // 无向图 0-6
    graph->InitializeWeights(
        { {0, 1}, {0, 5}, {1, 2}, {1, 6}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {4, 6} },
        { 25, 9, 16, 13, 11, 22, 19, 23, 24 }); // 初始化边

    vector<Graphs::MinimumSpanningTree::KruskalEdge> edges;
    AMGraphInt* minTree = Graphs::MinimumSpanningTree::Kruskal(graph, edges);

    cout << "----------克鲁斯卡尔 Kruskal----------" << endl;
    cout << "无向图:" << endl;
    cout << "邻接矩阵:" << endl;
    PrintMatrix(*graph);
    cout << endl;

    cout << "克鲁斯卡尔最小生成树的图:" << endl;
    PrintMatrix(*minTree);
    cout << endl;

    cout << "生成边顺序为:" << endl;
    for (int i = 0; i < edges.size(); i++)
    {
        cout << (char)(edges[i].second + 'A');
        cout << " ---" << edges[i].weight << "--- ";
        cout << (char)(edges[i].first + 'A') << endl;
    }
    cout << "--------------------" << endl;

    delete graph;
    delete minTree;

    cout << endl;
}

// 普利姆 Prim
void TestPrim()
{
    AMGraphInt* graph = new AMGraphInt({ 0, 1, 2, 3, 4, 5, 6 }, false); // 无向图 0-6
    graph->InitializeWeights(
        { {0, 1}, {0, 5}, {1, 2}, {1, 6}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {4, 6} },
        { 25, 9, 16, 13, 11, 22, 19, 23, 24 }); // 初始化边

    vector<Graphs::MinimumSpanningTree::PrimEdge> edges;
    AMGraphInt* minTree = Graphs::MinimumSpanningTree::Prim(graph, 0, edges);

    cout << "----------普利姆 Prim----------" << endl;
    cout << "无向图:" << endl;
    cout << "邻接矩阵:" << endl;
    PrintMatrix(*graph);
    cout << endl;

    cout << "普利姆最小生成树的图:" << endl;
    PrintMatrix(*minTree);
    cout << endl;

    cout << "生成边顺序为:" << endl;
    for (int i = 0; i < edges.size(); i++)
    {
        cout << (char)(edges[i].first + 'A');
        cout << " ---" << edges[i].weight << "--- ";
        cout << (char)(edges[i].second + 'A') << endl;
    }
    cout << "--------------------" << endl;

    delete graph;
    delete minTree;

    cout << endl;
}

5.2 打印结果 (Print Output)

----------克鲁斯卡尔 Kruskal----------
无向图:
邻接矩阵:
   A  B  C  D  E  F  G
A  0  25 0  0  0  9  0
B  25 0  16 0  0  0  13
C  0  16 0  11 0  0  0
D  0  0  11 0  22 0  19
E  0  0  0  22 0  23 24
F  9  0  0  0  23 0  0
G  0  13 0  19 24 0  0

克鲁斯卡尔最小生成树的图:
   A  B  C  D  E  F  G
A  0  0  0  0  0  9  0
B  0  0  16 0  0  0  13
C  0  16 0  11 0  0  0
D  0  0  11 0  22 0  0
E  0  0  0  22 0  23 0
F  9  0  0  0  23 0  0
G  0  13 0  0  0  0  0

生成边顺序为:
A ---9--- F
C ---11--- D
B ---13--- G
B ---16--- C
D ---22--- E
E ---23--- F
--------------------

----------普利姆 Prim----------
无向图:
邻接矩阵:
   A  B  C  D  E  F  G
A  0  25 0  0  0  9  0
B  25 0  16 0  0  0  13
C  0  16 0  11 0  0  0
D  0  0  11 0  22 0  19
E  0  0  0  22 0  23 24
F  9  0  0  0  23 0  0
G  0  13 0  19 24 0  0

普利姆最小生成树的图:
   A  B  C  D  E  F  G
A  0  0  0  0  0  9  0
B  0  0  16 0  0  0  13
C  0  16 0  11 0  0  0
D  0  0  11 0  22 0  0
E  0  0  0  22 0  23 0
F  9  0  0  0  23 0  0
G  0  13 0  0  0  0  0

生成边顺序为:
A ---9--- F
F ---23--- E
E ---22--- D
D ---11--- C
C ---16--- B
B ---13--- G
--------------------

请按任意键继续. . .


上一篇:【基础算法】关于图论中最小生成树(Minimum Spanning Tree)那些不可告人的秘密


下一篇:ASP.NET MVC 基于角色的权限控制系统的示例教程