資料結構中的圖搜尋

我們知道圖是一種非線性資料結構。在這種資料結構中，我們將一些值放入節點中，並且節點透過不同的邊連線起來。由於我們可以將資料儲存到圖結構中，我們也需要從圖中搜索元素才能使用它們。

對於圖搜尋，有兩種不同的方法：廣度優先搜尋和深度優先搜尋技術。

廣度優先搜尋 (BFS)

廣度優先搜尋 (BFS) 遍歷是一種用於訪問給定圖的所有節點的演算法。在此遍歷演算法中，選擇一個節點，然後逐個訪問所有相鄰節點。完成所有相鄰頂點後，它將進一步檢查另一個頂點並再次檢查其相鄰頂點。要實現此演算法，我們需要使用佇列資料結構。當所有相鄰頂點都完成後，所有相鄰頂點都新增到佇列中，從佇列中移除一個專案並再次開始遍歷該頂點。

深度優先搜尋 (DFS)

深度優先搜尋 (DFS) 是一種圖遍歷演算法。在此演算法中，給定一個起始頂點，當找到一個相鄰頂點時，它首先移動到該相鄰頂點並嘗試以相同的方式遍歷。它儘可能地深入遍歷，之後回溯以到達之前的頂點以查詢新的路徑。

要以迭代方式實現 DFS，我們需要使用堆疊資料結構。如果我們想遞迴地執行它，則不需要外部堆疊，可以使用內部堆疊進行遞迴呼叫。

更新於：2020年8月10日

2K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告