什么是最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树[维基百科]

常见的应用例子有铺设道路连接所有城市、铺设管道等，目标都是使总长度最短。

求解最小生成树的基本原理

Prim算法和Kruskal算法是求解最小生成树的两种经典算法，这两个算法都是贪心算法。使用到了MST的一个性质：两个集合之间相连的最短的边一定属于两个集合组成的生成树。该性质的详细证明请见算法导论第23章。这里不赘述了。

Prim算法

概述

Prim算法讲点分为两个集合U和V-U，其中V为全部点的集合。每次从V-U中选择一个距离集合V最近的顶点v1加入U，并讲U中对应的顶点标记为v1的父节点。重复该过程，直到U=V

算法步骤

Step1：初始化U为空，并讲minCut[0]初始化为0，minCut其他值初始化为最大值，minCut用于记录V-U中顶点距离V的最小距离。初始化isInMST数组值为false，parent[0]置为-1，表示0节点没有父节点。

Step2：从minCut中选择值最小的节点v1作为下一个加入U的节点，

Step3：更新V-U中和v1相连的节点距离V的最小距离，即更新minCut数组，并将minCut值变小的节点的父节点(parent)标记为v1.

Step4：重复Step2和Step3，直到U=V，即全部节点都已经加入了集合U。

Step5：此时最小生成树的信息记录在了parent数组中

C++实现

vector<int> primMST (vector<vector<int>> &graph)
{
    if(graph.size() == 0)
    {
        return vector<int>();
    }
    vector<int> parents(graph.size(), -1);
    vector<bool> isInMst(graph.size(), false);
    vector<int> minCut(graph.size(), INT_MAX);
    minCut[0] = 0;
    for(int i = 0; i < isInMst.size(); i++) //每次循环，选择一个顶点加入MST集合中，总共n次循环，即顶点个数
    {
        int index = findNextVertex(isInMst, minCut);
        isInMst[index] = true;
        for(int i = 0; i < minCut.size(); i++)
        {
            if(graph[index][i] != 0 && graph[index][i] < minCut[i])
            {
                minCut[i] = graph[index][i];
                parents[i] = index;
            }
        }
    }
    return parents;
}

int findNextVertex (vector<bool> &isInMst, vector<int> &minCut)
{
    int minDist = INT_MAX;
    int index = -1;
    for(int i = 0; i < isInMst.size(); i++)
    {
        if(isInMst[i] == false && minCut[i] < minDist)
        {
            minDist = minCut[i];
            index = i;
        }
    }
    return index;
}

Kruskal算法

概述

给边按照边长排序，然后每次选择一个权重最小的并且两个顶点不属于同一个集合的边作为新边加入结果集中，重复该过程，直到结果集中包含n-1条边。最小生成树的变长一定是顶点数减去1，该算法需要判断两个点是否在同一个集合中，以及合并两个集合。

算法步骤

Step1：根据边的权重对边按照非递减顺序排序。

Step2：选择权重最小的且两个顶点属于两个不同集合的边加入结果集，并合并该边两个顶点所在的两个集合

Step3：重复Step2直到结果集中包含n-1个边。

Step4：此时结果集记录了最小生成树的所有边

补充说明：

Step2中需要使用到disjont-set forests的find和union操作，使用parent来记录顶点所在集合。采用union by rank 和path compression两种优化方式进行实现，详细算法请参考算法导论第21章。

Kruskal中的parent数组仅用于存储顶点的集合信息，最小生成树存储在边的结果集中，Prim算法中parent数组用于记录每个顶点加入顶点的结果集时的前驱节点，所以parent记录了最小生成树。

C++实现

/*
 * Step1: 给所有边按照weight排序
 * Step2：寻找连接两个独立的点集合的权重最小的边，将连个集合组成一个集合（使用find和union操作）
 * Step3：重复Step2，直到找到的边数达到n-1个（最小生成树一定是n-1个边，n为顶点数）
 */
vector<vector<int>> kruskalMST (vector<vector<int>> &graph)
{
    if(graph.size() == 0)
    {
        return vector<vector<int>>();
    }
    //获取边并排序
    vector<vector<int>> edges;
    vector<vector<int>> mstEdges;
    for(int i = 0; i < graph.size(); i++)
    {
        for(int j = i + 1; j < graph.size(); j++)
        {
            if(graph[i][j] != 0)
            {
                edges.push_back({i, j, graph[i][j]});
            }
        }
    }
    sort(edges.begin(), edges.end(), [] (vector<int> &a, vector<int> &b){ return a[2] < b[2]; });
    //执行n-1次，每次获得连接两个独立点集合的权重最小的边
    vector<int> parents(graph.size(), -1);
    vector<int> rank(graph.size(), 0); //代表最长的路径有几条边。
    for(int i = 0; i < edges.size(); i++)
    {
        if(isCut(parents, edges[i][0], edges[i][1]))
        {
            mstEdges.push_back(edges[i]);
            unionSet(parents, rank, edges[i][0], edges[i][1]);
            if(mstEdges.size() == graph.size() - 1)
            {
                break;
            }
        }
    }
    return mstEdges;
}

bool isCut (vector<int> &parents, int v1, int v2)
{
    int root1 = findRoot(parents, v1);
    int root2 = findRoot(parents, v2);
    if(root1 == root2)
    {
        return false;
    }else
    {
        return true;
    }
}

void unionSet (vector<int> &parents, vector<int> &rank, int v1, int v2)
{
    int root1 = findRoot(parents, v1);
    int root2 = findRoot(parents, v2);
    if(rank[root1] = rank[root2])
    {
        parents[root2] = root1;
        rank[root1]++;
    }else if(rank[root1] < rank[root2])
    {
        parents[root1] = root2;
    }else
    {
        parents[root2] = root1;
    }
}

int findRoot (vector<int> &parents, int v)
{
    if(parents[v] == -1)
    {
        return v;
    }
    int root = findRoot(parents, parents[v]);
    parents[v] = root;
    return root;
}