Wednesday, June 13, 2007

BFS? Bigger-faster-stronger?

今天政螢學弟問我 BFS (breadth-first search) 的 complexity,我就 Google 了一下找答案。有你的,第一個找到的東西居然是:


Bigger - Faster- Stronger

有你的!


話說回來,BFS 的 time complexity 是 O(V + E),對於 graph traversal (or searching on a graph) on unweighted graphs 也是一個 optimal algorithm。

No comments: