最小生成樹MST：Prim算法和Kruskal算法

什麼是最小生成樹

最小生成樹是一副連通權重無向圖中一棵權值最小的生成樹[維基百科]

常見的應用例子有鋪設道路連接配接所有城市、鋪設管道等，目标都是使總長度最短。

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

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() == )
    {
        return vector<int>();
    }
    vector<int> parents(graph.size(), -);
    vector<bool> isInMst(graph.size(), false);
    vector<int> minCut(graph.size(), INT_MAX);
    minCut[] = ;
    for(int i = ; i < isInMst.size(); i++) //每次循環，選擇一個頂點加入MST集合中，總共n次循環，即頂點個數
    {
        int index = findNextVertex(isInMst, minCut);
        isInMst[index] = true;
        for(int i = ; i < minCut.size(); i++)
        {
            if(graph[index][i] !=  && 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 = -;
    for(int i = ; 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() == )
    {
        return vector<vector<int>>();
    }
    //擷取邊并排序
    vector<vector<int>> edges;
    vector<vector<int>> mstEdges;
    for(int i = ; i < graph.size(); i++)
    {
        for(int j = i + ; j < graph.size(); j++)
        {
            if(graph[i][j] != )
            {
                edges.push_back({i, j, graph[i][j]});
            }
        }
    }
    sort(edges.begin(), edges.end(), [] (vector<int> &a, vector<int> &b){ return a[] < b[]; });
    //執行n-1次，每次獲得連接配接兩個獨立點集合的權重最小的邊
    vector<int> parents(graph.size(), -);
    vector<int> rank(graph.size(), ); //代表最長的路徑有幾條邊。
    for(int i = ; i < edges.size(); i++)
    {
        if(isCut(parents, edges[i][], edges[i][]))
        {
            mstEdges.push_back(edges[i]);
            unionSet(parents, rank, edges[i][], edges[i][]);
            if(mstEdges.size() == graph.size() - )
            {
                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] == -)
    {
        return v;
    }
    int root = findRoot(parents, parents[v]);
    parents[v] = root;
    return root;
}