一些概念

连通图

图论中,连通图基于连通的概念。在一个无向图 G 中,若从顶点i 到顶点 j 有路径相连(当然从 j 到 i 也一定有路径),则称 i 和 j 是连通的。如果 G 是有向图,那么连接 i 和 j 的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。

生成树

包含图的全部顶点,边数最少的连通子图

最小生成树

总权值最小的生成树

常见问题(该算法)就是求最小生成树。
并查集

是一个数据结构,功能有查找 a 和 b 是否为同一组;将 a 和 b 合并为同一组。

算法思路

把所有边按照权值全部按数值大小拿出来,然后按顺序选取每条边,利用并查集的思想,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。

比如有如下这么一个图:
image.png
单独分析 ①② 边和 ③④ 边情况下,两个不在一个集合里面,
image.png
不断重复,不断判断是否为同一个集合,不在同一个集合的话,就合并,持续如此。比方说当一直操作到权值为 3 的时候,此时就需要将左右两个集合合并了
image.png
最后的结果样式就为如下
image.png

代码实现

#include <stdio.h>
#include <vector>
#include <algorithm>
namespace NS_KruskalMST {
using namespace std;
void KruskalMST();
int FindSet(int u);
void UnionSets(int u, int v);
void Initialization();
void GenEdges();
void MakeSets();
void Output(int v0);
#define INF INT_MAX
static int n;
static vector<vector<int>> WMatrix;
static vector<pair<pair<int, int>, int>> Edges;
//Node struct for the disjoint set
struct DJSNode {
    int Parent; int Rank;
    DJSNode(int p) : Parent(p), Rank(0) {}
};
static vector<DJSNode> DisjointSet;
static vector<pair<int, int>> MST;
//The adjacency list for MST
static vector<vector<int>> MSTList;
static vector<int> Prev;
void KruskalMSTCaller(int an,
    vector<vector<int>> &wMatrix, int v0)
{
    n = an;
    WMatrix = wMatrix;
    Initialization();
    KruskalMST();
    Output(v0);
}
void KruskalMST()
{
    for (auto &e: Edges)
    {
        int u = e.first.first;
        int v = e.first.second;
        int setU = FindSet(u);
        int setV = FindSet(v);
        if (setU != setV)
        {
            MST.push_back(e.first);
            if (MST.size() == n - 1)
                break;
            UnionSets(setU, setV);
        }
    }
}
int FindSet(int u)
{
    while (u != DisjointSet[u].Parent)
        u = DisjointSet[u].Parent;
        //For path compression:
        //DisjointSet[u].Parent =
        //    FindSet(DisjointSet[u].Parent);
    return u;
}
void UnionSets(int u, int v)
{
    if (DisjointSet[u].Rank >= DisjointSet[v].Rank)
        DisjointSet[v].Parent = u;
    else
        DisjointSet[u].Parent = v;
    if (DisjointSet[u].Rank == DisjointSet[v].Rank)
        DisjointSet[u].Rank++;
}
void Initialization()
{
    GenEdges();
    sort(Edges.begin(), Edges.end(),
        [](pair<pair<int, int>, int>a,
            pair<pair<int, int>, int>b)
        {return a.second < b.second; });
    MakeSets();
    MST.clear();
}
void GenEdges()
{
    Edges.clear();
    //Traverse the upper triangle of WMatrix
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
            if (WMatrix[i][j] != INF)
                Edges.push_back({ {i, j},
                    WMatrix[i][j] });
    }
}
void MakeSets()
{
    DisjointSet.clear();
    for (int i = 0; i < n; i++)
        DisjointSet.push_back(DJSNode(i));
}
void OutputWMatrix()
{
    printf("n = %d\n", n);
    printf("The weight matrix:\n");
    printf("%3c", ' ');
    for (int j = 0; j < n; j++)
        printf("%3d", j + 1);
    printf("\n");
    for (int i = 0; i < n; i++)
    {
        printf("%3d", i + 1);
        for (auto j : WMatrix[i])
            if (j < INF)
                printf("%3d", j);
            else
                printf("%3c", '*');
        printf("\n");
    }
}
void OutputPath(int u)
{
    if (Prev[u] == -1)
        printf("%d", u + 1);
    else
    {
        OutputPath(Prev[u]);
        printf("-%d", u + 1);
    }
}
void GenMSTList()
{
    MSTList.clear();
    MSTList.resize(n);
    for (auto &e: MST)
    {
        MSTList[e.first].push_back(e.second);
        MSTList[e.second].push_back(e.first);
    }
}
void GenPrev(int v)
{
    for (auto &u : MSTList[v])
        if (u != -1)
        {
            Prev[u] = v;
            auto w = find(MSTList[u].begin(),
                MSTList[u].end(), v);
            MSTList[u][w - MSTList[u].begin()] = -1;
            GenPrev(u);
        }
}
void Output(int v0)
{
    printf("Kruskal's MST algorithm\n");
    OutputWMatrix();
    int wSum = 0;
    for (int i = 0; i < n - 1; i++)
        wSum += WMatrix[MST[i].first][MST[i].second];
    GenMSTList();
    Prev.clear();
    Prev.resize(n);
    Prev[v0] = -1;
    GenPrev(v0);
    printf("The MST edges:\n");
    printf("Edge Weight\n");
    for (auto &e : MST)
        printf(" %d-%d  %d\n", e.first + 1, e.second + 1,
            WMatrix[e.first][e.second]);
    printf("Total MST weight: %d\n", wSum);
    printf("The MST paths from vertex %d:\n", v0 + 1);
    for (int u = 0; u < n; u++)
        if (u != v0)
        {
            printf("%3d: ", u + 1);
            OutputPath(u);
            printf("\n");
        }
    printf("\n");
}
} //namespace NS_KruskalMST
using namespace NS_KruskalMST;
void TestKruskalMST(int v0 = 0)
{
    vector<vector<vector<int>>> w = {
        //https://www.geeksforgeeks.org/
        //prims-minimum-spanning-tree-mst-greedy-algo-5/
        {
            {   0,  2,INF,  6,INF },
            {   2,  0,  3,  8,  5 },
            { INF,  3,  0,INF,  7 },
            {   6,  8,INF,  0,  9 },
            { INF,  5,  7,  9,  0 }
        },
        // Dijkstra's algorithm on Wikipedia
        {
            {   0,  7,  9,INF,INF, 14 },
            {   7,  0, 10, 15,INF,INF },
            {   9, 10,  0, 11,INF,  2 },
            { INF, 15, 11,  0,  6,INF },
            { INF,INF,INF,  6,  0,  9 },
            {  14,INF,  2,INF,  9,  0 },
        },
        //https://www.geeksforgeeks.org/
        //kruskals-minimum-spanning-tree-using-stl-in-c/
        {
            {   0,  4,INF,INF,INF,INF,INF,  8,INF },
            {   4,  0,  8,INF,INF,INF,INF, 11,INF },
            { INF,  8,  0,  7,INF,  4,INF,INF,  2 },
            { INF,INF,  7,  0,  9, 14,INF,INF,INF },
            { INF,INF,INF,  9,  0, 10,INF,INF,INF },
            { INF,INF,  4, 14, 10,  0,  2,INF,INF },
            { INF,INF,INF,INF,INF,  2,  0,  1,  6 },
            {   8, 11,INF,INF,INF,INF,  1,  0,  7 },
            { INF,INF,  2,INF,INF,INF,  6,  7,  0 },
        },
    };
    int k = w.size();
    for (int i = 0; i < k; i++)
    {
      if (v0 > w[i].size() - 1)
        v0 = w[i].size() - 1;
      KruskalMSTCaller(w[i].size(), w[i], v0);
    }
}