1

People always talk about how if there are infinite nodes downwards, then DFS will get stuck traversing this infinitely long branch and never reaching the answer in another branch.

Isn't this applicable to BFS as well? For example if the root node has an infinite amount of neighbours, wouldn't the program just spend an infinite amount of time trying to add each one into a queue?

terrabyte
  • 307
  • 1
  • 3
  • 12
  • theoretically yes, but chances of having an infinite number of neighbors vs an infinite depth is lower, IMO. Even if it was so, you can much easier get an estimate of what's going on in your neighborhood than what's up in the deepest branches of a graph. – user1984 Dec 02 '21 at 09:44
  • Related: [Is it possible to design a tree where nodes have infinitely many children?](https://stackoverflow.com/questions/22618703/is-it-possible-to-design-a-tree-where-nodes-have-infinitely-many-children) – Stef Dec 02 '21 at 14:02
  • Did any of the answers below suit your needs? Any feedback? – trincot Dec 07 '21 at 12:02

2 Answers2

4

In some cases, yes.

However, in order to have an infinite graph you basically need an implicit graph, https://en.wikipedia.org/wiki/Implicit_graph and many of them have bounded degree which avoids that problem.

Additionally, another advantage with BFS over DFS is that a path with fewer vertices often is "better" in some way - and by having a cost for the vertices that can be formulated using algorithms like Djikstra's that in some cases can be extended even to unbounded degrees.

Hans Olsson
  • 11,123
  • 15
  • 38
1

Yes you are right, in the second case BFS will not have any real progress. For this theoretical infinite scenarios, let's discuss all the three possible cases:

  1. If the graph had infinite nodes downwards and finite neighbors, then we should use BFS (you already explained the reason)
  2. But if the graph has infinite neighbors and finite nodes downwards, then we should use DFS as in this case while doing DFS search for each neighbor we would be able to search it's complete path in finite time and then move on to the next neighbor. Here, BFS wouldn't have gotten any real progress while searching.
  3. If graph had both infinite neighbors and infinite nodes downwards, then DFS and BFS will seize to differ as we are dealing with infinity on both ends.
robinjagal
  • 31
  • 3