我們收可以看下面這幅圖，用深度和廣度兩種方法來遍歷這個圖形的點。

題目.png

使用深度優(yōu)先搜索來遍歷這個圖的過程具體是：首先從一個未走到過得頂點作為起始頂點，比如以1號作為起點，沿1號頂點的邊去嘗試訪問其它未走到過得頂點，首先發(fā)現(xiàn)2號頂點還沒有走到過，于是來到2號頂點。再以2號頂點作為出發(fā)點繼續(xù)嘗試訪問其它未走到過得頂點，這樣又來到了4號頂點。再以4號頂點作為出發(fā)點繼續(xù)嘗試訪問其它未走到過得頂點。但是，此時沿4號頂點的邊，已經(jīng)不能訪問到其它未走到過得頂點了，所以需要返回2號頂點。返回到2號頂點后，發(fā)現(xiàn)沿2號頂點的邊也不能在訪問到其它未走到過得頂點。因此還需要繼續(xù)返回到1號頂點。在繼續(xù)沿1號頂點的邊看看還能否訪問到其它未走到過的頂點。此時又會來到3號頂點，再以3號頂點作為出發(fā)點繼續(xù)訪問其它未走到過的頂點，于是又來到5號頂點。到此，所有頂點都已經(jīng)走到過了，遍歷結(jié)束。如下圖顯示路徑：

深度廣義搜索.png

現(xiàn)在來總結(jié)一下深度優(yōu)先搜索的主要思想就是：首先以一個未被訪問過得頂點作為起始頂點，沿當(dāng)前頂點的邊走到未訪問過得頂點；當(dāng)沒有未訪問過的頂點時，則回到上一個頂點，繼續(xù)試探訪問別的頂點，直到所有頂點都被訪問過。顯然，深度優(yōu)先遍歷是沿著圖的某一條分支遍歷直到末端，然后回溯，再沿著另一條進行同樣的遍歷，直到所有的頂點都被訪問過為止。

接下來就來說說廣度優(yōu)先搜索怎么來遍歷這個圖，首先以一個未被訪問過得頂點作為起始頂點，比如以1號頂點作為起點。將1號頂點放入到隊列中，然后將與1號頂點相鄰的未被訪問過的頂點即2號、3號和5號頂點依次再放入隊列中。接下來再將2號頂點相鄰的未訪問過的頂點4號頂點4號放入到隊列中。到此所有頂點都被訪問過，遍歷結(jié)束。

廣度優(yōu)先搜索.png

廣度優(yōu)先遍歷的主要思想就是：首先以一個未被訪問過的頂點作為起始頂點，訪問其所有相鄰的頂點，然后對每個相鄰的頂點，再訪問它們相鄰的未被訪問過的頂點，直到所有頂點都被訪問過，遍歷結(jié)束。

以上就深度優(yōu)先和廣度優(yōu)先的主要思想。