Kruskal算法用链表判断回路C++实现

Kruskal算法是一种基于贪心思想的最小生成树算法，其中一个重要的步骤是判断当前加入边是否会形成回路。下面是使用链表实现判断回路的C++代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 定义边的结构体
struct Edge {
    int from;   // 起点
    int to;     // 终点
    int weight; // 权重
};

// 定义节点的结构体
struct Node {
    int parent; // 父节点
    int rank;   // 秩（用于优化并查集）
};

// 并查集查找操作
int find(vector<Node>& nodes, int i) {
    if (nodes[i].parent != i) {
        nodes[i].parent = find(nodes, nodes[i].parent);
    }
    return nodes[i].parent;
}

// 并查集合并操作
void unite(vector<Node>& nodes, int i, int j) {
    int root_i = find(nodes, i);
    int root_j = find(nodes, j);
    if (root_i == root_j) {
        return;
    }

    // 按秩合并
    if (nodes[root_i].rank > nodes[root_j].rank) {
        nodes[root_j].parent = root_i;
    } else if (nodes[root_i].rank < nodes[root_j].rank) {
        nodes[root_i].parent = root_j;
    } else {
        nodes[root_j].parent = root_i;
        nodes[root_i].rank++;
    }
}

// Kruskal算法求最小生成树
vector<Edge> kruskal(vector<Edge>& edges, int n) {
    // 初始化节点
    vector<Node> nodes(n);
    for (int i = 0; i < n; i++) {
        nodes[i].parent = i;
        nodes[i].rank = 0;
    }

    // 按边权值从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    // 遍历所有边
    vector<Edge> mst; // 最小生成树的边集合
    for (const auto& edge : edges) {
        if (find(nodes, edge.from) != find(nodes, edge.to)) {
            mst.push_back(edge);
            unite(nodes, edge.from, edge.to);
        }
    }

    return mst;
}

int main() {
    int n = 5; // 节点个数
    vector<Edge> edges = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 3}, {2, 3, 5}, {2, 4, 6}, {3, 4, 4}}; // 边集合

    vector<Edge> mst = kruskal(edges, n); // 求最小生成树

    for (const auto& edge : mst) { // 输出最小生成树的边集合
        cout << edge.from << " -> " << edge.to << " : " << edge.weight << endl;
    }

    return 0;
}

代码中使用了并查集来判断加入边是否会形成回路，同时按边权值从小到大排序，保证每次加入的边都是当前可选边中权值最小的。