兩點間所有路徑的遍歷算法

1、兩點間所有途徑的遍歷算法中國海洋大學(xué)信息科學(xué)與工程學(xué)院熊建立梁磊摘要：本文首先簡單介紹圖的深度優(yōu)先遍歷算法，接著根據(jù)圖的深度優(yōu)先遍歷算法求出連通圖中兩點間所有途徑。一、深度優(yōu)先遍歷（Depth-FirstTraversal）1.圖的深度優(yōu)先遍歷的遞歸定義假設(shè)給定圖G的初態(tài)是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發(fā)點（源點），那么深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點v,并將其標(biāo)記為已訪問過；然后依次從v出發(fā)搜索v的每個鄰接點wo假設(shè)w未曾訪問過，那么以w為新的出發(fā)點繼續(xù)進(jìn)展深度優(yōu)先遍歷，直至圖中所有和源點v有途徑相通的頂點（亦稱為從源點可達(dá)的頂點）均已被訪問為止。假設(shè)此時圖中仍有未訪

2、問的頂點，那么另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂點均已被訪問為止。圖的深度優(yōu)先遍歷類似于樹的前序遍歷。采用的搜索方法的特點是盡可能先對縱深方向進(jìn)展搜索。這種搜索方法稱為深度優(yōu)先搜索（Depth-FirstSearch）。相應(yīng)地，用此方法遍歷圖就很自然地稱之為圖的深度優(yōu)先遍歷。2、深度優(yōu)先搜索的過程設(shè)x是當(dāng)前被訪問頂點，在x做過訪問標(biāo)記后，選擇一條從x出發(fā)的未檢測過的邊（x,y）。假設(shè)發(fā)現(xiàn)頂點y已訪問過，那么重新選擇另一條從x出發(fā)的未檢測過的邊，否那么沿邊（x,y）到達(dá)未曾訪問過的y,對y訪問并將其標(biāo)記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有途徑，即訪問

3、完所有從y出發(fā)可達(dá)的頂點之后，才回溯到頂點x,并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。此時，假設(shè)x不是源點，那么回溯到在x之前被訪問過的頂點；否那么圖中所有和源點有途徑相通的頂點（即從源點可達(dá)的所有頂點）都已被訪問過，假設(shè)圖G是連通圖，那么遍歷過程完畢，否那么繼續(xù)選擇一個尚未被訪問的頂點作為新源點，進(jìn)展新的搜索過程。、求兩點間所有途徑的算法假設(shè)簡單連通圖如圖1所示，那么它的鄰接表存儲構(gòu)造如圖2所示。假設(shè)我們要找出結(jié)點3到結(jié)點6的所有途徑，那么，我們就設(shè)結(jié)點3為起點，結(jié)點6為終點。我們需要的存儲構(gòu)造有：一個保存途徑的棧、一個保存已標(biāo)記結(jié)點的數(shù)組，那么找到

4、結(jié)點3到結(jié)點6的所有途徑步驟如下：1我們建立一個存儲結(jié)點的棧構(gòu)造，將起點3入棧，將結(jié)點3標(biāo)記為入棧狀態(tài)；2 從結(jié)點3出發(fā)，找到結(jié)點3 從結(jié)點1出發(fā)，找到結(jié)點4 從結(jié)點0出發(fā)，找到結(jié)點5 從結(jié)點2出發(fā)，找到結(jié)點6 從結(jié)點5出發(fā)，找到結(jié)點3 的第一個非入棧狀態(tài)的鄰結(jié)點1 的第一個非入棧狀態(tài)的鄰結(jié)點0 的第一個非入棧狀態(tài)的鄰結(jié)點2 的第一個非入棧狀態(tài)的鄰結(jié)點5 的第一個非入棧狀態(tài)的鄰結(jié)點1，將結(jié)點1標(biāo)記為入棧狀態(tài)；0，將結(jié)點0標(biāo)記為入棧狀態(tài)；2，將結(jié)點2標(biāo)記為入棧狀態(tài)；5，將結(jié)點5標(biāo)記為入棧狀態(tài)；6，將結(jié)點6標(biāo)記為入棧狀態(tài)；7 棧頂結(jié)點6是終點，那么，我們就找到了一條起點到終點的途徑，輸出這條途徑；8 從棧頂彈出結(jié)點6，將6標(biāo)記為非入棧狀態(tài)；9 如今棧頂結(jié)點為5，結(jié)點5沒有除終點外的非入棧狀態(tài)的結(jié)點，所以從棧頂將結(jié)點5彈出；10如今棧頂結(jié)點為2，結(jié)點2除了剛出棧的結(jié)點5之外，還有非入棧狀態(tài)的結(jié)點6，那么我們將結(jié)點6入棧；11如今棧頂為結(jié)點6，即找到了第二條途徑，輸出整個棧，即為第二條途徑12重復(fù)步驟2-11，就可以找到從起點3到終點6的所有途徑；13棧為空，算法完畢。三總結(jié)本算法利用無向圖的鄰接