最小生成樹算法(Kruskal) C++實作

代碼參考來源

//
//  main.cpp
//  KruskalMST
//
//  Created by YangZai on 22.04.21.
//

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

/* 并查集(Disjoint-Set)節點(node)的定義 */
typedef struct _dsetNode
{
    // 節點的值/名字
    char data;
    // 目前節點作為代表節點時集合的大小(包含節點的數量)，僅當為代表節點時有意義
    int rank;
    // 節點的父母節點
    _dsetNode *parent;
}dsetNode;

/* 記錄某一時刻集合的數目 */
int count = 0;

/* map用節點值/名字來擷取節點的位址 */
map<char, dsetNode*> mymap;

/* MakeSet函數根據節點值建構節點，并将其存進mymap中 */
void MakeSet(char data)
{
    dsetNode* node = new dsetNode;
    node->data = data;
    mymap[data] = node;
    // 初始rank為1，代表集合包含1個節點即節點本身
    node->rank = 1;
    // 初始節點的父母節點為節點本身
    node->parent = node;
    // ::(作用域運算符)用來指定通路全局變量裡的count
    ::count++;
}

/*
 函數FindSetRoot輸入是一個節點的指針，傳回該節點所在集合的代表節點的指針，這裡用了路徑壓縮，
 也就是說在查找過程中經過的節點都會直接連在代表節點的後面，以後這些節點的查找時間複雜度就是O(1)。
 */
dsetNode *FindSetRoot(dsetNode *node)
{
    if (node != node->parent)
    {
        node->parent = FindSetRoot(node->parent);
    }
    return node->parent;
}

/* FindSet函數根據節點值來擷取該節點所在集合的代表節點值 */
char FindSet(char x)
{
    dsetNode *node = mymap[x];
    node = FindSetRoot(node);
    return node->data;
}

/* isconnected函數檢查兩個節點所在集合是否相連即是否屬于同一集合 */
bool isconnected(char x, char y)
{
    return (FindSet(x) == FindSet(y));
}

/* LinkSet函數用來合并兩個集合，rank值小的要合并到rank值大的集合裡 */
void LinkSet(char x, char y)
{
    if (isconnected(x, y))
    {
        return;
    }
    dsetNode *node1 = mymap[x];
    dsetNode *node2 = mymap[y];
    if (node1->rank > node2->rank)
    {
        node2->parent = node1;
        // 合并完以後更新rank值
        node1->rank += node2->rank;
    }
    else
    {
        node1->parent = node2;
        node2->rank += node1->rank;
    }
    // 每合并兩個集合則總集合數量減1
    ::count--;
}

/* UnionSet函數用來調用LinkSet來合并兩個集合 */
void UnionSet(char x, char y)
{
    LinkSet(FindSet(x), FindSet(y));
}

/* freeset用來釋放程式運作過程中動态申請的記憶體，防止記憶體洩漏 */
void freeset(char arr[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        dsetNode *node = mymap[arr[i]];
        delete node;
    }
}

/* QuickSort原地快速排序 */
void QuickSort(int array[], int low, int high, char edgein[], char edgeout[])
{
    int i = low, j = high;
    // 使用中間位置的值為中軸
    int pivot = array[(low + high)/2];
    
    while (i <= j)
    {
        while (array[i] < pivot)
        {
            ++i;
        }
        while (array[j] > pivot)
            
        {
            --j;
        }
        
        if (i <= j)
        {
            // 交換i和j位置的數
            int i_tmp = array[i];
            array[i] = array[j];
            array[j] = i_tmp;
            
            char c_tmp = edgein[i];
            edgein[i] = edgein[j];
            edgein[j] = c_tmp;
            
            c_tmp = edgeout[i];
            edgeout[i] = edgeout[j];
            edgeout[j] = c_tmp;
            
            ++i;
            --j;
        }
    }
    
    // 遞歸對子序列進行排序
    if (i < high)
    {
        QuickSort(array, i, high, edgein, edgeout);
    }
    if (j > low)
    {
        QuickSort(array, low, j, edgein, edgeout);
    }
}

/* MSTKruskal函數用來得到最小生成樹 */
void MSTKruskal(char vertices[], char edgein[], char edgeout[], int weight[], int n, int m)
{
    // 建立初始化節點
    for (int i = 0; i < n; ++i)
    {
        MakeSet(vertices[i]);
    }
    
    // 根據權重對邊界進行非降序排序
    QuickSort(weight, 0, m-1, edgein, edgeout);
    
    int A = 0;
    cout << "最小生成樹包含的邊界：" << endl;
    /*
     i用來周遊所有邊界，count代表目前集合的數目，如果隻剩一個集合了，
     就說明已經得到最小生成樹了，可以提前結束循環。
     */
    for (int i = 0; i < m && ::count > 1; ++i)
    {
        // 如果目前邊界會造成環則忽略，即邊界兩端節點屬于同一集合
        if (isconnected(edgein[i], edgeout[i]))
        {
            continue;
        }
        
        // 将邊界添加到最小生成樹中，即合并邊界兩端節點所在的集合
        UnionSet(edgein[i], edgeout[i]);
        A += weight[i];
        cout << "\t" << edgein[i] << "--" << edgeout[i] << endl;
    }
    cout << "最小生成樹總共的權重為： " << A << endl;
    
    // 釋放用new動态申請的記憶體，防止記憶體洩漏
    freeset(vertices, n);
}


int main(int argc, const char * argv[]) {
    char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F'};

    char edgein[] = {'A', 'A', 'A', 'B', 'B', 'C', 'C', 'D', 'D'};
    char edgeout[] = {'B', 'D', 'C', 'D', 'E', 'D', 'F', 'E', 'F'};
    int weight[] = {6, 5, 3, 8, 2, 2, 6, 5, 3};
    
    // 節點數目n和邊界數目m
    int n = sizeof(vertices) / sizeof(vertices[0]);
    int m = sizeof(weight) / sizeof(weight[0]);
    MSTKruskal(vertices, edgein, edgeout, weight, n, m);
    
    return 0;
}

/*
 輸出：
 最小生成樹包含的邊界：
     B--E
     C--D
     D--F
     A--C
     D--E
 最小生成樹總共的權重為： 15
 */