我讀過關於BFS和DFS算法的頁面和頁面信息。他們沒有說什麼,首先選擇哪個頂點?BFS&DFS - 以哪個頂點開始?
例如,在這張圖片中,箭頭是否意味着您不能從c遍歷到b,但是可以從b遍歷到c?
你的幫助深表感謝,朋友。
我讀過關於BFS和DFS算法的頁面和頁面信息。他們沒有說什麼,首先選擇哪個頂點?BFS&DFS - 以哪個頂點開始?
例如,在這張圖片中,箭頭是否意味着您不能從c遍歷到b,但是可以從b遍歷到c?
你的幫助深表感謝,朋友。
如果它不是有向圖,那沒關係。 您發佈的圖形是一個有向圖,它的含義與您所說的完全相同。你可以從a到b而不是從b到a。
關於在有向圖中選擇哪個節點,您選擇的每個節點都可能產生不同的結果。通常在這種情況下,最好從根節點開始,如果給定的話。
do the arrows mean you cannot traverse from c to b, but can traverse from b to c?
這是一個有向圖,是。
當您執行DFS時,您不需要指定啓動哪個節點,因爲您將遍歷所有節點。
DFS的過程是:
DFSmain(G):
For v=1 to n: if v is not yet visited, do DFS(v).
DFS(v):
mark v as visited. // entering node v
for each unmarked out-neighbor w of v: do DFS(w).
return. // exiting node v.
因此,這將最終訪問的每個節點在圖中。 BFS的基本原理。
Breadth-first_search和Depth-first_search可以與任何來源頂點小號啓動。
要選擇哪個頂點作爲源頂點? - Depends upon your requirement
。
例:
如果你想找到所有使用BFS(與具有相同的成本或加權圖的所有邊緣圖)的 其他頂點的從信號源S的最短路徑那麼你應該選擇S作爲源頂點。
如果你想找到ķ是否頂點從頂點可達小號或 沒有,在這種情況下也必須從源頭 頂點S.啓動BFS/DFS
如果你想解決大鼠在迷宮問題,其中大鼠從源S開始,並且必須使用DFS到達目的地,然後再次必須從源S開始DFS算法。
In some Cases, We are free to choose any vertex as a source vertex
。
例:
雖然發現強連通分量(SCC)的有向圖的, 我們通過選擇任何一個頂點作爲源頂點開始DFS。
使用DFS執行有向無環圖 的拓撲排序時,我們也可以自由選擇任何頂點作爲源頂點。
因此,哪個頂點選擇第一不是固定的,取決於問題的性質,我們正在與DFS和BFS解決。
起始頂點是搜索的參數。您在調用搜索時指定它,並且搜索僅訪問從起始頂點可到達的頂點。 –
事實上,他們並沒有說這是因爲「廣度優先」和「深度優先」只是指您訪問節點的順序。起始節點取決於你想要達到的目標。 –