深度優先搜尋 (DFS)
深度優先搜尋 (DFS) 演算法以深度優先的方式遍歷圖，並使用堆疊來記住在任何迭代中遇到死衚衕時下一個要開始搜尋的頂點。
如上例所示，DFS演算法首先從S遍歷到A，再到D，G，E，B，然後到F，最後到C。它遵循以下規則。
規則1 - 訪問相鄰的未訪問頂點。將其標記為已訪問。顯示它。將其壓入堆疊。
規則2 - 如果找不到相鄰頂點，則從堆疊中彈出頂點。（它將彈出堆疊中所有沒有相鄰頂點的頂點。）
規則3 - 重複規則1和規則2，直到堆疊為空。
| 步驟 | 遍歷 | 描述 |
|---|---|---|
| 1 |  |
初始化堆疊。 |
| 2 |  |
將S標記為已訪問並將其放入堆疊。探索S的任何未訪問的相鄰節點。我們有三個節點，我們可以選擇其中任何一個。在本例中，我們將按字母順序選擇節點。 |
| 3 |  |
將A標記為已訪問並將其放入堆疊。探索A的任何未訪問的相鄰節點。S和D都與A相鄰，但我們只關心未訪問的節點。 |
| 4 |  |
訪問D，將其標記為已訪問並放入堆疊。這裡，我們有B和C節點，它們與D相鄰，並且都未被訪問。但是，我們將再次按字母順序選擇。 |
| 5 |  |
我們選擇B，將其標記為已訪問並放入堆疊。這裡B沒有任何未訪問的相鄰節點。所以，我們將B從堆疊中彈出。 |
| 6 |  |
我們檢查堆疊頂部以返回到上一個節點，並檢查它是否有任何未訪問的節點。在這裡，我們發現D位於堆疊的頂部。 |
| 7 |  |
現在，D唯一未訪問的相鄰節點是C。所以我們訪問C，將其標記為已訪問並放入堆疊。 |
廣告