畫出如下圖的鄰接表，并分別給出從結(jié)點(diǎn)1開始進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的結(jié)果？鄰接表如下圖所示：深度優(yōu)先遍歷過程如下：0->1->4->8->5（回溯8），8->6->2->

畫出如下圖的鄰接表，并分別給出從結(jié)點(diǎn)1開始進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷的結(jié)果？

鄰接表如下圖所示：深度優(yōu)先遍歷過程如下：0->

1->4->8->5（回溯8），8->6->

2->7（回溯0），0->3寬度優(yōu)先遍歷過程如下：0->1->2->3，1->4->5，2->6->7，4->8。上面的數(shù)字是索引，您給出的圖中的節(jié)點(diǎn)號(hào)加上1。

采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的先序遍歷，為什么是先序呢？

這是因?yàn)閳D的深度優(yōu)先遍歷算法首先訪問節(jié)點(diǎn)，然后訪問其相鄰點(diǎn)。它類似于二叉樹的順序遍歷，首先訪問子樹的根節(jié)點(diǎn)，然后訪問子樹的子節(jié)點(diǎn)（鄰接點(diǎn)）。圖的廣度優(yōu)先遍歷算法類似于二叉樹的層次遍歷。

用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常采用()來實(shí)現(xiàn)算法？

堆棧用于實(shí)現(xiàn)算法。在用鄰接表表示深度優(yōu)先遍歷的圖形時(shí)，通常采用堆棧實(shí)現(xiàn)，用隊(duì)列實(shí)現(xiàn)寬度遍歷。擴(kuò)展材質(zhì)：深度優(yōu)先遍歷：類似于樹的前序遍歷。從圖中的一個(gè)頂點(diǎn)v開始，訪問該頂點(diǎn)，然后從v的不可訪問鄰接點(diǎn)開始遍歷，直到訪問圖中與v相連的所有頂點(diǎn)。注意：優(yōu)先訪問外部節(jié)點(diǎn)。當(dāng)沒有新的頂點(diǎn)時(shí)，它將返回以訪問不可訪問的分支頂點(diǎn)。寬度優(yōu)先遍歷：類似于樹序列遍歷。從圖中的頂點(diǎn)w開始，讓頂點(diǎn)w加入隊(duì)列，然后讓頂點(diǎn)w離開隊(duì)列，讓與頂點(diǎn)w連接的所有頂點(diǎn)加入隊(duì)列，然后讓頂點(diǎn)t加入隊(duì)列，讓與t連接但未訪問的所有頂點(diǎn)加入隊(duì)列此循環(huán)指定圖中的所有元素都不在隊(duì)列中。數(shù)據(jù)結(jié)構(gòu)中的圖遍歷算法研究