天天看點

資料結構-圖-周遊-搜尋

參考:​​https://www.bilibili.com/video/BV1qt411171S​​

周遊定義:

從已給的連通圖中某一頂點出發, 沿着-一些邊訪遍圖中所有的頂點,且使每個頂點僅被通路一次,就叫做圖的周遊,它是圖的基本運算。

周遊實質:

找每個頂點的鄰接點的過程。

圖中可能存在回路:且圖的任一頂點都可能與其它頂點相通,在通路完某介頂點之後可能會沿着某些邊又回到了曾經通路過的頂點。

解決辦法:

設定輔助數組visited[n ],用來标記每個被通路過的頂點。

初始狀态visited [i]為0.

頂點i被通路,改visited [i]為1,防止被多次通路.

深度優先搜尋(Depth First Search--DFS ):

[類似一條道走到黑!]

1,一直往前走。直到無路可走!

資料結構-圖-周遊-搜尋

2,選擇回退找尋沒有點亮的燈。找到之後,進行點亮。同理沒有可以點亮的燈之後,再次回退。

一直到回退到入口【就是開始的地方!】:

資料結構-圖-周遊-搜尋

 官方總結:

資料結構-圖-周遊-搜尋
資料結構-圖-周遊-搜尋

廣度優先搜尋( Breadth Frist Search- BFS)

參考:​​https://www.bilibili.com/video/BV1qt41117Cu​​