最小生成树Kruskal算法实现C++实现

系统管理员 2022-05-15 13:21 287阅读 0赞

**// Kruskal算法实现.cpp : Defines the entry point for the console application.  
//**

**\#include "stdafx.h"  
\#include<iostream>  
\#define MAX 100  
typedef int WeiType;  
using namespace std;**

**//  
struct Edge  
\{  
int no; //边的序号  
int x; //端点1序号  
int y; // 端点2序号  
WeiType weight; //权值  
bool selected; //是否被选择  
\};**

**//边集和  
Edge edge\[MAX\];  
//已找到的最小生成树其中一部分的秩  
int rank\[MAX\];  
//已找到的最小生成树其中一部分的头结点  
//用来判断一条边的2个端点是否在一个集合中，即加上这条边是否会形成回路  
int parent\[MAX\];**

**//找出每一集合的头结点  
int find\_set(int x)  
\{  
if(x != parent\[x\] )  
parent\[x\] = find\_set(parent\[x\]);  
return parent\[x\];  
\}**

**//合并集合  
void union\_set(int x,int y,WeiType w,WeiType &sum)  
\{  
if(x==y)  
return;  
if(rank\[x\]>rank\[y\])  
parent\[y\]=x;  
else  
\{  
if(rank\[x\]==rank\[y\])  
rank\[y\]++;  
parent\[x\]=y;  
\}  
sum +=w;  
\}**

**//依据边的权值升序快速排序  
void fast\_sort(Edge \*edge,int begin,int end)  
\{  
if(begin<end)  
\{  
int i = begin-1,j=begin;  
edge\[0\] = edge\[end\];  
while(j<end)  
\{  
if(edge\[j\].weight<edge\[0\].weight)  
\{  
i++;  
Edge temp1 = edge\[i\];  
edge\[i\] = edge\[j\];  
edge\[j\] = temp1;  
\}  
j++;  
\}  
Edge temp2 = edge\[end\];  
edge\[end\] = edge\[i+1\];  
edge\[i+1\] = temp2;  
fast\_sort(edge,begin,i);  
fast\_sort(edge,i+2,end);  
\}  
\}**

**int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int cases;  
cout<<"请输入案例的个数：";  
cin>>cases;  
while(cases--)  
\{  
int n;  
//最小生成树的权值总和  
WeiType sum = 0;  
cout<<"请输入边的个数：";  
cin>>n;  
int i;  
//初始化  
char chx,chy;  
WeiType weight;  
for(i=1;i<=n;i++)  
\{  
edge\[i\].no = i;  
cout<<"请输入第"<<i<<"条边的二个端点的名称(小写字符)：";  
cin>>chx>>chy;  
edge\[i\].x = chx-'a'+1;  
edge\[i\].y = chy-'a'+1;  
cout<<"这条边的权值为：";  
cin>>weight;  
edge\[i\].weight = weight;  
edge\[i\].selected = false;  
parent\[edge\[i\].x\] = edge\[i\].x;  
parent\[edge\[i\].y\] = edge\[i\].y;  
rank\[edge\[i\].x\] = 0;  
rank\[edge\[i\].y\] = 0;  
\}  
//快排  
fast\_sort(edge,1,n);  
for(i=1;i<=n;i++)  
\{  
int x,y;  
x = find\_set(edge\[i\].x);  
y = find\_set(edge\[i\].y);  
//判断即加上这条边是否会形成回路  
if(x != y )  
\{  
//选择这条边  
edge\[i\].selected = true;  
//合并不会形成回路的二个集合  
union\_set(x,y,edge\[i\].weight,sum);  
\}  
\}  
cout<<"最小生成树的边集为："<<endl;  
for(i=1;i<=n;i++)  
\{  
if(edge\[i\].selected)  
\{  
cout<<"序号："<<edge\[i\].no<<" " <<"端点1："<<(char)(edge\[i\].x+'a'-1)<<",端点2："<<(char)(edge\[i\].y+'a'-1)<<endl;  
\}  
\}  
cout<<"最小生成树的权值为："<<sum<<endl;  
\}  
system("pause");  
return 0;  
\}**

**-------------------------------------------程序测试-------------------------------------------**

**![0_1320746882OilI.gif][]**

**请输入案例的个数：1  
请输入边的个数：14  
请输入第1条边的二个端点的名称(小写字符)：a b  
这条边的权值为：4  
请输入第2条边的二个端点的名称(小写字符)：a h  
这条边的权值为：8  
请输入第3条边的二个端点的名称(小写字符)：b c  
这条边的权值为：8  
请输入第4条边的二个端点的名称(小写字符)：b h  
这条边的权值为：11  
请输入第5条边的二个端点的名称(小写字符)：c d  
这条边的权值为：7  
请输入第6条边的二个端点的名称(小写字符)：c f  
这条边的权值为：4  
请输入第7条边的二个端点的名称(小写字符)：c i  
这条边的权值为：2  
请输入第8条边的二个端点的名称(小写字符)：d e  
这条边的权值为：9  
请输入第9条边的二个端点的名称(小写字符)：d f  
这条边的权值为：14  
请输入第10条边的二个端点的名称(小写字符)：e f  
这条边的权值为：10  
请输入第11条边的二个端点的名称(小写字符)：f g  
这条边的权值为：2  
请输入第12条边的二个端点的名称(小写字符)：g h  
这条边的权值为：1  
请输入第13条边的二个端点的名称(小写字符)：g i  
这条边的权值为：6  
请输入第14条边的二个端点的名称(小写字符)：h i  
这条边的权值为：7  
最小生成树的边集为：  
序号：12 端点1：g,端点2：h  
序号：11 端点1：f,端点2：g  
序号：7 端点1：c,端点2：i  
序号：1 端点1：a,端点2：b  
序号：6 端点1：c,端点2：f  
序号：5 端点1：c,端点2：d  
序号：3 端点1：b,端点2：c  
序号：8 端点1：d,端点2：e  
最小生成树的权值为：37  
请按任意键继续. . .**

[0_1320746882OilI.gif]: /images/20220515/45b78a51caa74679bb3bd9909af2258d.png