第二题.cpp

按克鲁斯卡尔（Kruskal）算法思想

//2．按克鲁斯卡尔（Kruskal）算法思想，编制一个寻找最小生成树的完整的程序。

#include<iostream.h>
#include<stdlib.h>
#define MAX_VEX 20                               //最大顶点个数   
#define INFINITY 99                             //最大值


struct Arc                                       //边结点
{
	int adj;                                     //记录权值
	int tag;                                     //标志位
};

struct Vex                                       //顶点
{
   char adj;
   int pos;
   int group;                                    //记录该顶点在第几组连通分量
}; 
                     
class Graph
{
  public:
	  Vex  vexs[MAX_VEX];                         //顶点向量
	  Arc  arcs[MAX_VEX][MAX_VEX]  ;              //邻接矩阵
	  int  vexnum,arcnum;
	  Graph();
	  void Initiate();
	  void Locate(int & pos ,char & x);
      void Display(); 
	  void Kruskal();
	  void FindMinArc(int & i,int & j);        //寻找权值最小的一条边
	  void MergeArcs(int & i,int & j);         //合并两个顶点到同一个连通分量
	  bool JudgeArc(int & i,int & j);          //判断一条边的两个顶点是否在同一连通分量中
};

void Graph::Locate(int & pos,char & x)
{ 
    for(int a=1;a<=vexnum;a++)
	{
		if(vexs[a].adj==x)
		{pos=a;return;}
	}
	cout<<"图中没有含有这个值的定点!"<<endl;abort();
}

Graph::Graph()
{   vexnum=0;arcnum=0;
	for(int i=0;i<MAX_VEX;i++)
	{vexs[i].adj=' ';vexs[i].pos=i;vexs[i].group=i;}
	for(i=0;i<MAX_VEX;i++)
		for(int j=0;j<MAX_VEX;j++)
		{arcs[i][j].adj=INFINITY;arcs[i][j].tag=0;}
}

void Graph::Initiate()
{
	cout<<"请输入顶点数目："; cin>>vexnum;
	for(int i=1;i<=vexnum;i++)
	{
		cout<<"请输入第"<<i<<"个顶点:";
		cin>>vexs[i].adj;
	}
	cout<<"请输入边的数目：";cin>>arcnum;
	for(i=1;i<=arcnum;i++)
	{   char vex1,vex2;
	    int adj;
		cout<<"请输入第"<<i<<"条弧的两个端点及权值(vex1/vex2/adj):";
		cin>>vex1>>vex2>>adj;
		int pos1,pos2;Locate(pos1,vex1);Locate(pos2,vex2);
		arcs[pos1][pos2].adj=adj;arcs[pos2][pos1].adj=adj;
	}
}

void Graph::Display()
{ 
	for(int i=1;i<=vexnum;i++)
		cout<<"    "<<vexs[i].adj;
	cout<<endl;
	for(i=1;i<=vexnum;i++)
	{
		cout<<vexs[i].adj<<"   ";
		for(int j=1;j<=vexnum;j++)
			cout<<arcs[i][j].adj<<" ";
		cout<<endl;
	}
}

bool Graph::JudgeArc(int & i,int & j)
{
	if(vexs[i].group==vexs[j].group)
		return true;
	else return false;
}
void Graph::MergeArcs(int & i,int & j)
{   int old=vexs[j].group;
	for(int a=1;a<=vexnum;a++)
	{if(vexs[a].group==old)
	 vexs[a].group=vexs[i].group;
	}
	 
}
void Graph::FindMinArc(int & i, int & j)
{   do
{
	int min=999;
    for(int a=1;a<=vexnum;a++)
		for(int b=1;b<=vexnum;b++)
		{
			if(arcs[a][b].adj<=min&&arcs[a][b].tag==0)
			{
				min=arcs[a][b].adj; i=a;j=b;
			}
		}
    arcs[i][j].tag=1;
}while(JudgeArc(i,j));
}

void Graph::Kruskal()
{
   int count=1;int x,y;
   while(count!=vexnum)
   {
      FindMinArc(x,y);
	  cout<<"最小生成树中第"<<count<<"条边是:("<<vexs[x].adj<<","<<vexs[y].adj<<")"<<endl;
	  MergeArcs(x,y);
	  count=count+1;
   }
}


void main()
{
	Graph graph;
	graph.Initiate();
	graph.Display();
	graph.Kruskal();
}