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

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

//

#include "stdafx.h"

#include

#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

{

int i = begin-1,j=begin;

edge[0] = edge[end];

while(j

{

if(edge[j].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<<"请输入第"<

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<<"最小生成树的边集为："<

for(i=1;i<=n;i++)

{

if(edge[i].selected)

{

cout<<"序号："<

}

}

cout<<"最小生成树的权值为："<

}

system("pause");

return 0;

}

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

请输入案例的个数：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

请按任意键继续. . .