Timeline for Graph searching: Breadth-first vs. depth-first
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2020 at 7:14 | comment | added | Dr. Hans-Peter Störr | Parallelism is a good point, but I would not agree to your statement at all. BFS needs a shared datastructure between all threads, which can lead to a variety of problems and performance loss, especially if you use multiple connected machines. DFS, however, can easily be parallelized if you don't insist on the exact ordering in which the nodes are searched if you distribute the search through different subtrees to different nodes. | |
| Mar 13, 2012 at 18:16 | comment | added | Raphael | If DFS is otherwise advantageous in the given setting, you can apply BFS until you have spawned enough threads and continue with DFS. More specifically, you can do DFS and whenever you descend and there are not enough threads, spawn one for the next sibling. | |
| Mar 13, 2012 at 17:43 | history | answered | Suresh | CC BY-SA 3.0 |