廣度優先與深度優先搜索的輸入/輸出

Question

我的問題並不是真的關於任何一種搜索類型的機制。我覺得它比這更平凡 - 我不明白任何一個的輸入和輸出。更具體地說，在CLRS中，BFS將圖形和源節點作爲輸入，但DFS僅使用圖形。 DFS不關心你從哪裏搜索？

這就是輸入的混淆。輸出的混淆是，在DFS中，當你完成後，你有一個類似於表的結構來記錄每個節點的發現和結束時間，對嗎？您如何從中提取解決方案，即從源節點到目標節點的路徑？

我希望我有道理。謝謝！

編輯：這是我的意思是DFS沒有采取源節點。這是CLRS的DFS僞碼。我沒有看到它在任何地方採取源節點。我看到它所做的只是通過圖中的所有節點。

DFS(G) 
1 for each vertex u ∈ V[G] 
2 do color[u] ← WHITE 
3 π[u]← NIL 
4 time ← 0 
5 for each vertex u ∈ V[G] 
6 do if color[u] = WHITE 
7 then DFS-VISIT(u) 

DFS-VISIT(u) 
1 color[u] ← GRAY ✄ White vertex u has just been discovered. 
2 time ← time+1 
3 d[u] ← time 
4 for each v ∈ Adj[u] ✄ Explore edge (u,v). 
5 do if color[v] = WHITE 
6 then π[v] ← u 
7 DFS-VISIT(v) 
8 color[u] ← BLACK ✄ Blacken u;it is finished. 
9 f [u] ← time ← time+1 

Answer 1

輸入困惑：

特定DFS通過CLRS給出不關心你來自哪裏搜索。搜索的確切結果取決於V[G]中節點的排序。通常我認爲DFS的作爲來自節點，例如開始：

DFS-Simple(G, s) 
1 for each vertex u ∈ V[G] 
2 do color[u] ← WHITE 
3 π[u]← NIL 
4 time ← 0 
5 DFS-VISIT(s) 

CLRS的版本產生林（一個樹圖中的每個分量），而不是隻是一個單一的樹，這大概適合他們的目的更好。

輸出混亂：

的路徑由時間標記沒有被記錄，而是由父指針π。例如，給定一個節點v，您可以像這樣打印到其根節點的路徑：

Print-Path-To-Root(v) 
1 while v ≠ Nil 
2 do print v 
3  v ← π[v] 

Answer 2

BFS和DFS都作爲輸入源節點。

使用DFS進行尋路時，只需在找到節點時停下來，然後將堆棧一直處理到原始節點以查找路徑。