数据结构拓展习题：破圈法求最小生成树代码实现

题目：破圈算法是1975年由我国数学家管梅谷教授提出来的（       管梅谷.求最小树的破圈法[J].数学的实践与认识.1975,(4).38-41.）。其基本思想是在给定的图中任意找出一个环路，删去该环路中权最大的边，然后在余下的图中再任意找出一个回路，再删去这个新找出的回路中权最大的边，……，一直重复上述过程，直到剩余的图中没有回路。剩余图便是最小生成树。

bool visited[MAX_VERTEX_NUM];

bool IsConnect(MGraph G)

{

       DFS(G, 0);

       for (int i = 0; i < G.vexnum; i++)

              if (!visited[i])

                     return false;

       return true;

}

MGraph MinSpanTree_BreakCircle(MGraph G)

{

       int arcNum = G.arcnum;//统计边的个数

       int i, j;

       int p = -1, q = -1;//标记上一轮找到的要删去的边的两个顶点序号

       int p_temp, q_temp;//记录这一轮找到的要删去的边的两个顶点序号

       int weigh = 10000;//存储权值大但不能删除的边的权值

//误删导致图不连通时还原该边

       while (arcNum + 1 > G.vexnum)//树的顶点数比边数多1，不然不是树

       {

              int max = 0;//记录环路中准备删除的边的权值

              for (i = 0; i < G.vexnum; i++)//在邻接矩阵的上三角位置查找可删除的边

              {

                     for (j = i; j < G.vexnum; j++)

                     {

                            //查找条件：权值次大边，即权值小于等于上一轮找到的最大权

                            //取等是因为可能存在好几条权值一样的边

                            if ((G.arcs[i][j].adj > max) && (G.arcs[i][j].adj <= weigh))

                            {

                                   //排除上一次找到但不能删去的边

                                   if (i != p || j != q)

                                   {

                                          max = G.arcs[i][j].adj;

                                          p_temp = i; q_temp = j;//储存权值最大元素的行列号

                                   }

                            }

                     }

              }

              weigh = max;

              p = p_temp;q = q_temp;

              G.arcs[p][q].adj = 0; //删除查找到的边

              G.arcs[q][p].adj = 0;

              if (IsConnect(G))//如果删除该边后图连通则删除成功

                     arcNum--;

              else//否则恢复该边，重新查找能删除的边

              {

                     G.arcs[p][q].adj = weigh;

                     G.arcs[q][p].adj = weigh;

              }

       }

       return G;

}