爲什麼BFS獲得最短路徑？

Question

BFS具有非常有用的屬性，如果 圖中的所有邊都是未加權的（或相同的權重），則第一次訪問節點 時是從源節點到該節點的最短路徑。

該屬性如何驗證？爲什麼不在DFS的情況下這樣的財產持有？

Answer 1

* A 
/\ 
| \ 
|  \ 
* B \ 
\  \ 
    \  \ 
    \  \ 
    * D \ 
    \  \ 
     \______* C 

看看這個簡單的圖。 例如，如果您要從A開始執行DFS，並且訪問的第一個鄰居將是頂點B，那麼您第一次訪問頂點C將通過D，因此您將獲得長度爲3的路徑。

因此，當A會尋找他的其他鄰居（C），他將不能訪問它，ABDC絕對不是從A到C

Answer 2

的最短路徑要回答你的問題，你應該先了解BFS和DFS在一般意義上工作。

考慮二叉搜索樹，這只是一個很簡單的圖，如下圖所示：

 *a 
    /\ 
    *b  *c 
/\ /\ 
    *d *e *f *g 

廣度優先搜索（BFS），正如它的名字所暗示的，將首先探索節點最接近源節點。假設你從節點* a開始搜索，BFS算法首先探測* b，接着* c，然後* d，* e，* f，* g。

深度優先搜索（DFS）另一方面，深度優先。從源節點* a開始，您將* expore *，然後* d，* e（直到您達到最終結果）。

因此，語句：

...一個節點訪問的第一個時間是從源節點

假設節點的最短路徑，爲BFS運行，你訪問了節點* b。這確實是從源節點到節點* b的最短路徑，因爲BFS具有總是首先探索最接近源節點的節點的屬性。

類似的概念可以應用於更復雜的圖。他們都工作一樣。

希望這會有所幫助！乾杯!