采用kruskal(克鲁斯卡尔) 算法求无向连通网图的一棵最小生成树。
#include
using namespace std;
const int MaxSize=6; // 顶点数
const int m=9; //边数
int vertexNum, arcNum; //顶点数和边数
char vertex[MaxSize]; //顶点数组
int parent[MaxSize];
struct EdgeType
{
int from, to;
int weight;
};
EdgeType edge[m];
void edgesz(char a[], int n, int e)
{
int i,j,k,w;
vertexNum=n; arcNum=e;
for (i=0; i
for (k=0; k
{
cin>>i>>j>>w; //边依附的两个顶点的序号及权值
edge[k].from=i;edge[k].to=j;edge[k].weight=w;
}
}
int FindRoot(int parent[], int v)
{
int t;
t=v;
while ( parent[t]>-1) t=parent[t];
return t;
}
void DubbleSort(EdgeType r[],int n)
{
int exchange,bound,j,k;
exchange=n-1; //第一趟的区间为1-- n
while(exchange) //当还未完全有序
{ bound=exchange; //传递本趟最后交换位置
exchange=0;
for(j=0;j
if (r[j].weight>r[j+1].weight)
{
k=r[j].from;r[j].from=r[j+1].from;r[j+1].from=k;
k=r[j].to;r[j].to=r[j+1].to;r[j+1].to=k;
k=r[j].weight;r[j].weight=r[j+1].weight;r[j+1].weight=k;
exchange=j; } //记录交换位置
}
}
//kruskal(克鲁斯卡尔) 算法
int main()
{
int i;
char a[MaxSize];
cout
for (i=0;i>a[i];
cout
DubbleSort(edge,m);
cout
Kruskal();
cout
return 0;
}