c++中如何实现Kruskal算法_c++ Kruskal算法实现方法

struct Edge {

  int u, v, weight;

立即学习“C++免费学习笔记（深入）”；

  Edge(int u, int v, int w) : u(u), v(v), weight(w) {}

};

bool cmp(Edge a, Edge b) {

  return a.weight < b.weight;

}

int find(vector<int>& parent, int x) {

  if (parent[x] != x)

    parent[x] = find(parent, parent[x]); // 路径压缩

  return parent[x];

}

void unite(vector<int>& parent, vector<int>& rank, int x, int y) {

  int rootX = find(parent, x);

  int rootY = find(parent, y);

  if (rootX != rootY) {

    if (rank[rootX] < rank[rootY])

      parent[rootX] = rootY;

    else if (rank[rootX] > rank[rootY])

      parent[rootY] = rootX;

    else {

      parent[rootY] = rootX;

      rank[rootX]++;

    }

  }

}

vector<Edge> kruskal(int n, vector<Edge>& edges) {

  vector<Edge> result;

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

31

查看详情

  sort(edges.begin(), edges.end(), cmp);

  vector<int> parent(n);

  vector<int> rank(n, 0);

  // 初始化并查集

  for (int i = 0; i < n; ++i)

    parent[i] = i;

  for (Edge& e : edges) {

    int u = e.u, v = e.v;

    if (find(parent, u) != find(parent, v)) { // 不连通

      result.push_back(e);

      unite(parent, rank, u, v); // 合并集合

    }

  }

  return result;

}

int main() {

  int n = 5;

  vector<Edge> edges;

  edges.push_back(Edge(0, 1, 2));

  edges.push_back(Edge(0, 3, 6));

  edges.push_back(Edge(1, 2, 3));

  edges.push_back(Edge(1, 3, 8));

  edges.push_back(Edge(1, 4, 5));

  edges.push_back(Edge(2, 4, 7));

  vector<Edge> mst = kruskal(n, edges);

  cout << "最小生成树的边：\n";

  for (Edge& e : mst) {

    cout << e.u << " -- " << e.v << " : " << e.weight << endl;

  }

  return 0;

}