作者falldog (嘿嘿~)
看板Prob_Solve
标题Re: [问题] 关於程式中的类型问题
时间Mon Aug 16 03:21:20 2004
※ 引述《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