求歐拉回路的一種解法
下面是無向圖的歐拉回路輸出代碼:注意輸出的前提是已經判斷圖確實是歐拉回路。
int num = 0;//標記輸出隊列
int match[MAX];//標志節點的度,無向圖,不區分入度和出度
void solve(int x)
{
if(match[x] == 0)
Record[num++] = x;
else
{
for(int k =1;k<=n;k++)
{
if(Array[x][k] !=0 )
{
Array[x][k]--;
Array[k][x]--;
match[x]--;
match[k]--;
solve(k);
}
}
Record[num++] = x;
}
}
注意record中的點的排列是輸出的到序,因此,如果要輸出歐拉路徑,需要將record倒過來輸出。
求歐拉回路的思路:
循環的找到出發點。從某個節點開始,然后查出一個從這個出發回到這個點的環路徑。這種方法保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點,這條邊為起始邊,把它和當前的環銜接上。這樣直至所有的邊都被遍歷。這樣,整個圖就被連接到一起了。
具體步驟:
1。如果此時與該點無相連的點,那么就加入路徑中
2。如果該點有相連的點,那馬就列一張表,遍歷這些點,知道沒有相連的點。
3。處理當前的點,刪除走過的這條邊,并在其相鄰的點上進行同樣的操作,并把刪除的點加入到路徑中去。
4。這個其實是個遞歸過程。