kruskal （克鲁斯卡尔）最小生成树的C++代码实现

#include "pch.h"

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

//一个克鲁斯卡尔kruskal算法-最小生成树的c++代码

struct edge

{

int first, last;                                //边的两个端点编号

int cost;                                //边权

edge(int x, int y, int c) :first(x), last(y), cost(c) {}

};

using namespace std;

//二进制函数，接受范围中的两个元素作为参数，并返回可转换为bool的值

bool comp(edge a, edge b)    //b>a 是从小往大了排。b<a 是从大到小排

{

return a.cost < b.cost;

}

//并查集查询函数，返回x所在集合的根节点

//关键性函数！查找给出的顶点的根节点

int FindFather(vector<int> father, int f)

{

int a = f;

while (father[a] != -1)

a = father[a];

return a;

}

//kruskal algorithem

int kruskal(int n, int m, vector<edge>& E)    //n是顶点个数,m 是边的个数，E是边的集合

{

vector<int> father(n);

int sum = 0;

int sum_edge = 0;

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

father[i] = -1;

sort(E.begin(), E.end(), comp);                        //STL中自带了sort函数用来对给定区间的所有元素进行排序.

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

{

int f_first = FindFather(father, E[i].first);

int f_last = FindFather(father, E[i].last);

//判断两个顶点的根节点是否是同一个，不是的话就说明两个“树”不是联通的，然后令f_last的根节点等于first，使其连通，就实现了合并

if (f_first != f_last)       

{

father[f_last] = f_first;

sum += E[i].cost;

sum_edge++;

if (sum_edge == (n - 1))

break;

}

}

if (sum_edge != (n - 1))

return 0;

else

return sum;

}

int main()

{

vector<edge> E = { edge(0,1,4),edge(1,2,1),edge(2,3,6),edge(3,4,5),edge(0,4,1),

  edge(0,5,2),edge(1,5,3),edge(2,5,5),edge(3,5,4),edge(4,5,3) };

int n = 6;

int m = 10;

int res = kruskal(n, m, E);

cout << res << endl;

}

结果输出为  11

有问题的朋友可以评论区提问，一起讨论共同进步