0
votes

BFS consumes a lot of memory especially when the branching factor of the tree is huge. DFS, on the other hand, may take a long time to visit other neighbouring nodes if the depth of the tree is huge, but it has better space-complexity. For example, in BFS, if I have a branching factor of 10 and depth of 12, using the formula O(b^d), it means I'll have around 10^12 nodes. If each node is 10Bytes, it'll need around 10TB.

However, what is considered 'huge' here? Is a 10TB space-complexity considered huge (I'm pretty sure it is, though)? How do I determine when I should leave DFS and BFS and look for other algorithms? Are they even still used in modern applications or are some other better algorithms applied instead (like IDDFS)?

1

1 Answers

0
votes

Consider this source: When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

I think there are experiment for your own data, resources. If the result of test case is not satisfying for you, try another algorithm. Binary-Tree Search, KDTree is some options.

If the memory is limited, try to use Disk to save the current state of search.