格拉夫檢查是否路徑三個節點

問題之間存在被以下我們必須找到至C這會突破下面的示例曲線圖甲 -G-F- 乙 -L- Ç節點B或從A路徑。格拉夫檢查是否路徑三個節點

現在實現從A到C很容易使用BFS，但我不知道如何確保這條路徑通過B？

2017-06-18 Master Yi

是您的圖形指示？我們是否需要找到**簡單的路徑**？ – DAle

'路徑'你可能是'簡單路徑' - 一個沒有重複頂點的路徑。

首先，確保A，B和C已連接。

的甲-...-乙-..- C路線存在當且僅當：

2017-06-19 07:23:17

http://c2n.me/3Lr1pya。在這個圖表中，你永遠不會通過'B'使用BFS達到'C'。 – DAle

@DAle：謝謝。回答修改。 –

@LiorKogan但你會如何找到路徑？ – fafl

首先運行一個bfs到達中間節點，然後從該中間節點運行一個bfs到所需的目標節點。

2017-06-18 15:24:55 guest3444343

否。這兩條路徑可能包含B旁邊的公共頂點。 –

@LiorKogan只保留訪問節點的列表，然後 – fafl

@fafl：仍然不好。 BFS算法中不同的頂點排序可能會給出不同的結果。 –

回答