用“破圈法”求解带权连通无向图的一棵最小代价生成树

我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法. 这也是复旦大学97年数据结构和操作系统的考研题.答案，亲测可用，c++编写工程。

// poquan.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h“


#include 
#include 

int n;  //存储结点数
int e;  //存储边数
#define maxvertexnum 50  //最大结点数

int visited[maxvertexnum];//标记结点是否被访问
float larr[maxvertexnum][maxvertexnum];//存储图的边的权值信息
typedef  struct  { int ijw;} myedge;  //顶点信息为顶点编号，权是整数
myedge* edge;


void createtree（）
{
  int ij;
  for（i=0;i	  for（j=0;j		  larr[i][j]=0;  //权值为0表示没有该边，即两个结点不邻接
  for（i=0;i	  visited[i]=0;
  printf（“请输入边数\n“）;
  scanf （ “%d“&e）;//输入边数
  printf（“请输入顶点数\n“）;
  scanf （ “%d“&n）;//输入顶点数
  edge=（myedge*）malloc（sizeof（myedge）*e）;
  
  printf（“请依次输入边的两个顶点的编号和边权值\n“）;
  for（i=1;i<=e;i++）  //输入e条边的顶点和权值
  {scanf（“%d%d%d“&edge[i].i&edge[i].j&edge[i].w）;
  larr[edge[i].i][edge[i].j]=edge[i].w;
  larr[edge[i].j][edge[i].i]=edge[i].w;
  }
}

//connect（k）是测试去掉边edge[k]后是否仍然连通，即是否能够DFS遍历完全
int connect（ int k）  
{  
    int temp=edge[k].w;  //先保存以备恢复
    edge[k].w=0;  //尝试删除边
	larr[ edge[k].i][ edge[k].j]=0;
	larr[ edge[k].j][ edge[k].i]=0;
	//非递归dfs遍历    
   //初始化 
   int top = -1 ; 
   int stack[1000]; //假设栈空间够用  
   int i;
   for（i=0;i   {
	  visited[i]=0; 
   }
   //从0结点开始遍历
    visited[0] = 1 ;  
	int count=1; //访问的结点数
    stack[++top] = 0 ;  
    while （ top != -1）  
    {  
        int v = stack[top] ;  
        for （ i = 0 ; i < n ; i++）  
        {  
            if （larr[v][i] !=0 &&!visited[i]）  
            {  
               
                visited[i] = 1 ; 
				count++;
                stack[ ++top ] = i ;  
                break ;  
            }  
        }  
        if（ i == n）  
        {  
            top -- ;  
        }  
    }
    if（count==n）  //仍然连通
	{
		return 1;
	}
	else
	{
	edge[k].w=temp;  //恢复边
	larr[ edge[k].i][ edge[k].j]=temp;
	larr[ edge[k].j][ edge[k].i]=temp;
	return 0;
	}	
      
}
void  spntree（）
{ 
  
  int ij;
    
  for（i=2;i<=e;i++）  //按权值大小，对边进行逆序排序
      { edge[0]=edge[i];
        j=i-1;
        while（edge[0].w>edge[j].w）  edge[j+1]=edge[j--];
        edge[j+1]=edge[0];
       }
	int k=1;
	int eg=e;
	while（eg>=n） //破圈，直到边数e=n-1
	{  if（connect（k））  //删除边edge[k]，若仍连通
		{edge[k].w=0;eg--;}  //权值置0表示该边被删除
	   k++;  //测试下一条边
	}//while
	printf（“最小生成树如下：\n“）;
	for （i=1;i<=e;i++）
	{
		if（edge[i].w!=0）
		{printf（“%d<->%d  %d\n“edge[i].iedge[i].jedge[i].w）;}
	}
}//算法结束
void main（）
{
	createtree（）;
	spntree（）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-03-02 08:36  12.poquan\
     目录           0  2015-03-02 08:42  12.poquan\poquan\
     目录           0  2015-03-02 08:36  12.poquan\poquan\Debug\
     文件       30720  2015-03-02 08:36  12.poquan\poquan\Debug\poquan.exe
     文件      313448  2015-03-02 08:36  12.poquan\poquan\Debug\poquan.ilk
     文件      429056  2015-03-02 08:36  12.poquan\poquan\Debug\poquan.pdb
     目录           0  2015-03-02 08:36  12.poquan\poquan\ipch\
     目录           0  2015-03-02 08:36  12.poquan\poquan\ipch\poquan-1033e1d7\
     文件     2359296  2015-03-02 08:36  12.poquan\poquan\ipch\poquan-1033e1d7\poquan-6c597ee0.ipch
     目录           0  2015-03-02 08:36  12.poquan\poquan\poquan\
     目录           0  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\
     文件        3026  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\CL.read.1.tlog
     文件         706  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\CL.write.1.tlog
     文件        1402  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\cl.command.1.tlog
     文件           2  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link-cvtres.read.1.tlog
     文件           2  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link-cvtres.write.1.tlog
     文件           2  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.28396-cvtres.read.1.tlog
     文件           2  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.28396-cvtres.write.1.tlog
     文件           2  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.28396.read.1.tlog
     文件           2  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.28396.write.1.tlog
     文件        1544  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.command.1.tlog
     文件        3416  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.read.1.tlog
     文件         768  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\link.write.1.tlog
     文件         364  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\mt.command.1.tlog
     文件         286  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\mt.read.1.tlog
     文件         286  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\mt.write.1.tlog
     文件         406  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\poquan.exe.embed.manifest
     文件         472  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\poquan.exe.embed.manifest.res
     文件         381  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\poquan.exe.intermediate.manifest
     文件          54  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\poquan.lastbuildstate
     文件        5102  2015-03-02 08:36  12.poquan\poquan\poquan\Debug\poquan.log
............此处省略21个文件信息