高中信息競(jìng)賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷(編輯修改稿)
2025-06-15 10:40 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 遍歷圖的算法是求解圖的連通性問(wèn)題、拓樸排序和求關(guān)鍵路徑等算法的基礎(chǔ)。通常有兩種遍歷方法： ⑴深度優(yōu)先搜索 (dfs) ⑵ 廣度優(yōu)先搜索 (bfs) 它們對(duì)無(wú)向圖和有向圖都適用。我們以相鄰矩陣存儲(chǔ)結(jié)構(gòu)給出深度優(yōu)先搜索和廣度優(yōu)先搜索的程序。 深度優(yōu)先搜索 深度優(yōu)先搜索類似于樹(shù)的前序遍歷 ， 是樹(shù)的前序遍歷的推廣 。 其搜索過(guò)程如下： 假設(shè)初始時(shí)所有結(jié)點(diǎn)未曾被訪問(wèn)。深度優(yōu)先搜索從某個(gè)結(jié)點(diǎn) V0出發(fā)，訪問(wèn)此結(jié)點(diǎn)。然后依次從 V0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 V0有路徑相連的結(jié)點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有結(jié)點(diǎn)未被訪問(wèn)，則另選一個(gè)未曾訪問(wèn)的結(jié)點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有結(jié)點(diǎn)都被訪問(wèn)為止。換句話說(shuō)，深度優(yōu)先搜索遍歷圖的過(guò)程是以 V0為起始點(diǎn)，由左而右，依次訪問(wèn)由 V0出發(fā)的每條路徑。 從 v3出發(fā) ， 按深度優(yōu)先搜索的順序遍歷 ，得到的結(jié)點(diǎn)序列是 v3→v 2→v 1→v 5→v 4。 深度優(yōu)先搜索 相鄰矩陣初始化； void dfs(int i)//深搜 { int j。 訪問(wèn)處理結(jié)點(diǎn) i。 f[i]=true。//置結(jié)點(diǎn) i為已訪問(wèn)標(biāo)記 for(j=1。j=n。j++)//按深度優(yōu)先搜索的順序遍歷 vi所有子樹(shù) if (!f[j]amp。amp。a[i][j]==1)dfs(j)。 } 調(diào)用一次 dfs(i),可按深度優(yōu)先搜索的順序訪問(wèn)處理結(jié)點(diǎn) i所在的連通分支 (或強(qiáng)連通分支 )。整個(gè)圖按深度優(yōu)先搜索順序遍歷的過(guò)程如下： void travel() { memset(f,0,sizeof(f))。 //置所有結(jié)點(diǎn)未訪問(wèn)標(biāo)志 for(i=1。i=n。i++) if(!f[i]) dfs(i)。 //深度優(yōu)先搜索每一個(gè)未訪問(wèn)的結(jié)點(diǎn) } 深度優(yōu)先搜索 廣度優(yōu)先搜索 廣度優(yōu)先搜索類似于樹(shù)的按層次遍歷的過(guò)程 ， 其搜索過(guò)程如下： 假設(shè)從圖中某結(jié)點(diǎn) v0出發(fā) ， 在訪問(wèn)了 v0之后依次訪問(wèn) v0的各個(gè)未曾訪問(wèn)的鄰接點(diǎn) ， 然后分別從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索的順序遍歷圖 ， 直至圖中所有可被訪問(wèn)的結(jié)點(diǎn)都被訪問(wèn)到 。若此時(shí)圖中尚有結(jié)點(diǎn)未被訪問(wèn) ， 則任選其中的一個(gè)作起始點(diǎn) ，重復(fù)上述過(guò)程 ， 直至圖中所有結(jié)點(diǎn)都被訪問(wèn)到為止 。 換句話說(shuō) ，按廣度優(yōu)先順序搜索遍歷圖的過(guò)程是以 v0為起始點(diǎn) ， 由近及遠(yuǎn) ，依次訪問(wèn)和 v0有路徑相連且路徑長(zhǎng)度為 1， 2， 3…… 的結(jié)點(diǎn) 。 從 v3出發(fā)按廣度優(yōu)先搜索的順序遍歷 ， 得到的結(jié)點(diǎn)序列是v3→v 2→v 4→v 1→v 5 由于隊(duì)列“先進(jìn)先出”的存取規(guī)則與廣度優(yōu)先搜索的遍歷順序相吻合，因此使用了一個(gè)工作隊(duì)列 q，按訪問(wèn)的先后順序存儲(chǔ)被訪問(wèn)過(guò)的結(jié)點(diǎn)序號(hào)。 memset(f,0,sizeof(f))。//訪問(wèn)標(biāo)志初始化 f[s]=true。q[1]=s。//訪問(wèn)源點(diǎn)，源點(diǎn)入隊(duì) open=1。closed=1。//隊(duì)列的首尾指針初始化 while(open=closed)//若隊(duì)列非空 ,則訪問(wèn)與隊(duì)首元素相連的未訪問(wèn)點(diǎn) ,計(jì)算其路徑長(zhǎng)度 ,并將它們送入隊(duì)列 { for(i=1。i=n。i++) if((f[i]==false)amp。amp。(a[q[open]][i]!=0)) {訪問(wèn)頂點(diǎn) i。f[i]=true。closed++。q[closed]=i。} open++。//出隊(duì) } } 調(diào)用一次 bfs(i)可按廣度優(yōu)先搜索的順序訪問(wèn)處理結(jié)點(diǎn) i所在的連通分支 (或強(qiáng)連通分支 )。整個(gè)圖按廣度優(yōu)先搜索順序遍歷的過(guò)程如下： void travel() { memset(f,0,sizeof(f))。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1