// 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;
}
-------------------------------------------程序測試-------------------------------------------
請輸入案例的個數：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
請按任意鍵繼續. . .
作者 heyongluoyao8
