Kruskal算法

Kruskal算法是贪心算法的典型例子。算法连续选择开销最小的边，除非这个边的两端都已被连入树中。

这个算法的关键在于“如何判断这个边是不是有效的”，需要用到并查集。而这个并查集的合并/查找操作相当密集，因此选用静态链表并查集。

先来写个并查集：

struct UFSNode {
    unsigned int classNum;
    unsigned int size;
    unsigned int next;
};

class UFSChain {
private:
    vector<UFSNode> arr;
public:
    UFSChain(int initSize = 0);
    void unite(int classA, int classB);
    int operator[](unsigned int index) const { return arr[index].classNum; }
};

UFSChain::UFSChain(int initSize) 
    : arr(initSize) {
    for (int i = 0; i < arr.size(); i++) {
        arr[i].classNum = i;
        arr[i].size = 1;
        arr[i].next = -1;
    }
}

void UFSChain::unite(int classA, int classB) {
    if (arr[arr[classA].classNum].size > arr[arr[classB].classNum].size) {
        swap(classA, classB);
    }
    int str = arr[classA].classNum;
    arr[arr[classB].classNum].size += arr[arr[classA].classNum].size;
    while (arr[str].next != -1) {
        arr[str].classNum = classB;
        str = arr[str].next;
    }
    arr[str].classNum = arr[classB].classNum;
    arr[str].next = arr[classB].next;
    arr[arr[classB].classNum].next = classA;
}

主要的算法代码是非常直观的。这里将边以权重从小到大排序来模拟小堆优化。

int kruskal(const vector<vector<int>> &Graph) {
    vector<vector<int>> edge;
    for (int i = 0; i < Graph.size(); i++) {
        for (int j = 0; j < Graph.size(); j++) {
            if (Graph[i][j] != 0) {
                edge.push_back({Graph[i][j], i, j});
            }
        }
    }

    sort(edge.begin(), edge.end(), [](vector<int> A, vector<int> B) {
        return A[0] < B[0];
    });

    int res = 0;
    UFSChain ufs(Graph.size());
    for (int i = 0; i < edge.size(); i++) {
        if (ufs[edge[i][1]] != ufs[edge[i][2]]) {
            res += edge[i][0];
            ufs.unite(edge[i][1], edge[i][2]);
        }
    }
    return res;
}

适用情况

Kruskal算法需要遍历所有的边，故适用于边稀疏的情况。