題目：破圈算法是1975年由我國數(shù)學(xué)家管梅谷教授提出來的（?????? 管梅谷.求最小樹的破圈法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí).1975,(4).38-41.）。其基本思想是在給定的圖中任意找出一個(gè)環(huán)路，刪去該環(huán)路中權(quán)最大的邊，然后在余下的圖中再任意找出一個(gè)回路，再刪去這個(gè)新找出的回路中權(quán)最大的邊，……，一直重復(fù)上述過程，直到剩余的圖中沒有回路。剩余圖便是最小生成樹。

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;//統(tǒng)計(jì)邊的個(gè)數(shù)

?????? int i, j;

?????? int p = -1, q = -1;//標(biāo)記上一輪找到的要?jiǎng)h去的邊的兩個(gè)頂點(diǎn)序號(hào)

?????? int p_temp, q_temp;//記錄這一輪找到的要?jiǎng)h去的邊的兩個(gè)頂點(diǎn)序號(hào)

?????? int weigh = 10000;//存儲(chǔ)權(quán)值大但不能刪除的邊的權(quán)值

//誤刪導(dǎo)致圖不連通時(shí)還原該邊

?????? while (arcNum + 1 > G.vexnum)//樹的頂點(diǎn)數(shù)比邊數(shù)多1，不然不是樹

?????? {

????????????? int max = 0;//記錄環(huán)路中準(zhǔn)備刪除的邊的權(quán)值

????????????? for (i = 0; i < G.vexnum; i++)//在鄰接矩陣的上三角位置查找可刪除的邊

????????????? {

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

???????????????????? {

??????????????????????????? //查找條件：權(quán)值次大邊，即權(quán)值小于等于上一輪找到的最大權(quán)

??????????????????????????? //取等是因?yàn)榭赡艽嬖诤脦讞l權(quán)值一樣的邊

??????????????????????????? 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;//儲(chǔ)存權(quán)值最大元素的行列號(hào)

?????????????????????????????????? }

??????????????????????????? }

???????????????????? }

????????????? }

????????????? 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//否則恢復(fù)該邊，重新查找能刪除的邊

????????????? {

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

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

????????????? }

?????? }

?????? return G;

}