※ 引述《iorilin (君 莫 殆 於 戲)》之銘言：
: 最近寫 acm 發現, 有一個類型叫做 BFS...
: 不知道誰可以解釋一下這個類型是再做什麼的 ?
: 我寫的題目是 acm 571...不太了解 BFS 是啥 ?
: 不知道誰可以幫幫我嗎?...謝謝 ^^
BFS
Breadth-First Search
廣度優先搜尋
就是說在一個connected graph中
給一vertex 從此vertex開始搜尋
會優先從連接此vertex的所有vertex開始搜尋
所以BFS的觀念就是QUEUE
ex:
a---b---c---e
| /
d-----f
|
g
從b點開始做BFS搜尋
(連接b點的a d c三點 搜尋的先後順序皆可)
搜尋順序 QUEUE
b
b adc
ba dc
bad cgf
badc gfe
badcg fe
badcgf e
badcgfe
所以搜尋的順序就是badcgfe
(當然答案可以有很多組囉 因為連接的vertex放入QUEUE的先後順序沒差)
有錯請指正~^^"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.73.69.6