[理工]ALGO BFS

[aa23032311 (what?)]

想請問一下在有向圖中做BFS時如圖下所示


http://ppt.cc/7vLE

由節點3開始

我做到節點4時發現下一個處理的會是節點2


但又發現假如選取節點2時會有cycle出現

想問說不管在做BFS或是DFS時這種情況發生

是否要將節點2(會發生cycle)的節點納入呢??

還是就停在目前節點4且結束呢?謝謝!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.120.80.19
推 pikachu123:他又不會走(2,5)這個邊 就一樣加入阿
→ pikachu123:DFS BFS都會產生spanning tree不過你那個圖不連通
→ pikachu123:就沒辦法找出spainig tree 一般我們都叫 DFS(BFS) Tree
推 rockmanray:你可能對BFS有點誤解 我們是先選點
→ rockmanray:當加入2的時候，會繼續判斷由2可以到的「5」是否要加入
→ rockmanray:可是5已經加入過了 所以不取5 所以由2到5邊也不取了
推 rockmanray:像kruskal..等決定MST的演算法 才是選邊(以邊為主)
→ rockmanray:可能這樣讓你誤會了