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

// 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;

}

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

补充：软件开发 , C++ ,

上一个：无向图的广度优先搜索（采用邻接表存储）C++实现
下一个：最小生成树Prim算法实现（采用邻接表存储）C++实现