三分钟搞懂kruskal算法、prim算法和dijkstra算法的区别(附kruskal算法的代码)

发布于:2021-10-18 14:31:48


kruskal的代码:


#include
#include
#include

using namespace std;

//一边和两点的结构
struct con{
int point1,point2,roadLength;//两个节点(孩子)和长度
}map[50005];

int p[1005];

bool cmp(con a,con b)
{
return a.roadLength}

//寻找根节点
int getfa(int point)
{
if(p[point]==point)
return p[point];
else
return getfa(p[point]);
}

int kruskal(int n,int m)
{
int sum=0,lineNum = 1;//sum用于计算最小生成树的总长度,而lineNum用于记录这是第几条被加入的边
for(int i=0;i p[i]=i;//开始时每个点都是独立的集合,根节点都是自己
sort(map,map+m,cmp);//边按权重从小到大排序
for(int i=0;i {
if(getfa(map[i].point1)!=getfa(map[i].point2))//如果一条边相连的两个点的根节点不同(则该边加入并不会形成回路)
{
p[getfa(map[i].point1)]=getfa(map[i].point2);//使这两个点的根节点相同
sum+=map[i].roadLength;//该边加入长度
cout<<"第"<< lineNum <<"条边:"<< map[i].roadLength << endl;
lineNum++;
}
}
cout << "最小生成树总长:";
return sum;
}

int main()
{
int point,line;
while(cin>>point && point!=0)//输入该图的点数
{
cin>>line;//输入该图边数
for(int i=0;i {
cin>>map[i].point1>>map[i].point2>>map[i].roadLength;//输入每个一边两点的数据(点的编号和边的长度)
}
cout< }
return 0;
}

相关推荐

最新更新

猜你喜欢