2013-04-01 37 views
4

我讀過關於BFS和DFS算法的頁面和頁面信息。他們沒有說什麼,首先選擇哪個頂點?BFS&DFS - 以哪個頂點開始?

例如,在這張圖片中,箭頭是否意味着您不能從c遍歷到b,但是可以從b遍歷到c?

search network

你的幫助深表感謝,朋友。

+0

起始頂點是搜索的參數。您在調用搜索時指定它,並且搜索僅訪問從起始頂點可到達的頂點。 –

+0

事實上,他們並沒有說這是因爲「廣度優先」和「深度優先」只是指您訪問節點的順序。起始節點取決於你想要達到的目標。 –

回答

1

如果它不是有向圖,那沒關係。 您發佈的圖形是一個有向圖,它的含義與您所說的完全相同。你可以從a到b而不是從b到a。

關於在有向圖中選擇哪個節點,您選擇的每個節點都可能產生不同的結果。通常在這種情況下,最好從根節點開始,如果給定的話。

1

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的基本原理。

5

Breadth-first_searchDepth-first_search可以與任何來源頂點小號啓動。

要選擇哪個頂點作爲源頂點? - Depends upon your requirement

  1. 如果你想找到所有使用BFS(與具有相同的成本或加權圖的所有邊緣圖)的 其他頂點的從信號源S的最短路徑那麼你應該選擇S作爲源頂點。

  2. 如果你想找到ķ是否頂點從頂點可達小號或 沒有,在這種情況下也必須從源頭 頂點S.啓動BFS/DFS

  3. 如果你想解決大鼠在迷宮問題,其中大鼠從源S開始,並且必須使用DFS到達目的地,然後再次必須從源S開始DFS算法。

In some Cases, We are free to choose any vertex as a source vertex

  1. 雖然發現強連通分量(SCC)的有向圖的, 我們通過選擇任何一個頂點作爲源頂點開始DFS。

  2. 使用DFS執行有向無環圖 的拓撲排序時,我們也可以自由選擇任何頂點作爲源頂點。

因此,哪個頂點選擇第一不是固定的,取決於問題的性質,我們正在與DFS和BFS解決。