456789.cpp

用C++做的破圈法求最小生成树

#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
#define VexMax 10
#define EdgeMax 45
#define WeightMax 100
#define null 0

int i,j,x,y;
int n,e,k;

bool visited[VexMax];
int AdjMatrix[VexMax][VexMax];


struct Edge
{   
	int   fromvex;   
	int   endvex;   
	int   weight;   
}temp,edge[EdgeMax];
 

struct ArcNode				/*定义弧结点 */
{ int adjvex;				/*邻接点序号 */
  ArcNode *nextarc;			/*指向下一个邻接点*/
  int weight;				/*存放权值*/
};

 struct VexNode				/*定义表头结点*/
{
	int vertex;				/*顶点编号*/
	ArcNode *firstarc;		/*指向第一条依附该结点的弧的指针*/
}AdjList[VexMax];




void main() 
{
   
	void sort();
	void CreateAdjMatrix();
	void AdjMatrixToAdjList();
	bool connect();
	void DeletEdge(int i,int j);
    void InsertEdge(int i,int j); 

	cout<<"请输入顶点数:";
	cin>>n;
	cout<<"请输入边数:";
	cin>>e; //输入顶点数和边数。
    cout<<"请依次输入各条边的始点 终点 权值:"<<endl;
	for(i=0;i<=e-1;i++)     //输入e条边:始点，终点，权值。
	cin>>edge[i].fromvex>>edge[i].endvex>>edge[i].weight;

	sort();//按边上的权值大小，对边进行排序。
	CreateAdjMatrix();
	AdjMatrixToAdjList();

	k=0;  
	int eg=e;
	while (eg>=n)                  //破圈，直到边数e=n-1.
	{DeletEdge(edge[k].fromvex,edge[k].endvex);//删除边
     if (connect()==true)               //删除第k条边后若仍连通。
	 {edge[k].weight=0; 
      eg--;         //测试下一条边edge[k]，权值置0表示该边被删除
      k++;} //下条边
     else{InsertEdge(edge[k].fromvex,edge[k].endvex);
	      k++;}//恢复
  

	}//while 
	cout<<"利用破圈法求出的最小生成数为:"<<endl;
	for(i=0;i<e;i++)
	{
	 if(edge[i].weight>0)
	  cout<<edge[i].fromvex<<"--"<<edge[i].endvex<<"="<<edge[i].weight<<endl;
	}

	system("pause");
	}//算法结束。

void sort() //按边上的权值大小，对边结点从大到小排序。
{ 
  bool change;
  for(i=e-1,change=true;i>=1&&change;i--)  
  {change=false;
   for(j=0;j<i;j++)
     if(edge[j].weight>edge[j+1].weight)
	 {
	     temp=edge[j];
	     edge[j]=edge[j+1];
	     edge[j+1]=temp;
	     change=true;
	  }
  }
    for(i=0;i<e/2;i++)
	{temp=edge[i];
	 edge[i]=edge[e-1-i];
	 edge[e-1-i]=temp;
	}
	 for(i=0;i<e;i++)
		 cout<<edge[i].weight<<endl;
}

void CreateAdjMatrix()     //创建邻接矩阵。
{ for(i=0;i<VexMax;i++)   
    for(j=0;j<VexMax;j++){   
       AdjMatrix[i][j]=0;}
	for(i=0;i<e;i++)
    {x=edge[i].fromvex;
	 y=edge[i].endvex;
	 AdjMatrix[x][y]=edge[i].weight;
	 AdjMatrix[y][x]=edge[i].weight;}
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	{cout<<AdjMatrix[i][j];
	if(j=n-1){cout<<endl;}
	}

}  
    

void AdjMatrixToAdjList() //将邻接矩阵转换成邻接表。
{ 
  struct ArcNode *p;
  for (i=0;i<n;i++) AdjList[i].firstarc=null;
   for(i=0;i<n;i++)
   {
    for(j=0;j<n;j++)
     if (AdjMatrix[i][j]!=0)
	 {
      p=new ArcNode(); 
	  p->adjvex=j;
      p->nextarc=AdjList[i].firstarc;//将P所指的结点插入链表
      p->weight=AdjMatrix[i][j];
      AdjList[i].firstarc=p;
	 }
   }

}//end


void DFS(int i)
{
 struct ArcNode *q;
 visited[i]=true;  
 q=AdjList[i].firstarc;
 while (q!=null){
	 visited[q->adjvex]=true;
	 q=q->nextarc;
 }
 for(j=0;j<n;j++)
  if(visited[j]==false)
	  DFS(j);
      
}
bool connect()
{
	
    void DFS(int i);
    DFS(0);
	for(i=0;i<n;i++)
	{if(visited[i]==false) 
	      return false;
	      break;
 
	}
  return true;
}

void DeletEdge(int i,int j) //在用邻接表方式存储的无向图g中，删除边(i,j)
{   struct ArcNode *p;
	p=AdjList[i].firstarc; //删顶点i 的边结点(i,j)
	while (p){
      if (p->adjvex==j)
	  {AdjList[i].firstarc=p->nextarc;
	   free(p);}//释放结点空间。

     else {p=p->nextarc;}   //沿链表继续查找
   }
    
	p=AdjList[j].firstarc; //删顶点j 的边结点(j,i)
	while (p){
       if (p->adjvex==i)
	   {AdjList[j].firstarc=p->nextarc;
	   free(p);}//释放结点空间。
	   else{p=p->nextarc;} }  //沿链表继续查找
}// DeletEdge

void InsertEdge(int i,int j) //在用邻接表方式存储的无向图g中，插入边(i,j)
{   struct ArcNode *p1,*p2;
     p1=new ArcNode();
     p1->nextarc=AdjList[i].firstarc; //插入点i 的边结点(i,j)
	 AdjList[i].firstarc=p1;

	 p2=new ArcNode();
     p2->nextarc=AdjList[j].firstarc; //插入点i 的边结点(i,j)
	 AdjList[j].firstarc=p1;
}//InsertEdge