4 ms·
Breadth-First Search (BFS) and Depth-First Search (DFS) are actually both pretty interesting algorithms (although relatively simple for the basic cases - there
by vram22 8y ago
Breadth-First Search (BFS) and Depth-First Search (DFS) are actually both pretty interesting algorithms (although relatively simple for the basic cases - there are some variations), partly because of their applications.
It's actually initially a bit surprising that BFS has such a simple algorithm using a queue, as mentioned elsewhere in this thread and in the Wikipedia article about it [1]. Might be non-intuitive on first look, but then turns out to make perfect sense.
[1] https://en.wikipedia.org/wiki/Breadth-first_search https://en.wikipedia.org/wiki/Breadth-first_search
https://en.wikipedia.org/wiki/Depth-first_search https://en.wikipedia.org/wiki/Depth-first_search
- megous 8y agoAnd this being front-end, ie. JS, you can just use map/flat in a loop to get breadth first traversal. function bfs(list, cb) { while (list.length > 0) { let i = list.find(cb); if (i) return i; list = list.map(i => i.cn || []).flat(); } }
- vram22 8y agoInteresting, thanks. The Go Programming Language book also has a couple of nice examples of DFS and BFS, in the middle chapters. One is for sorting courses by prerequisites, and the other is for a web crawler, IIRC.