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?

CodePudding user response：

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.

CodePudding user response：

There is no such thing as a graph with an infinite number of nodes. That would require an infinite amount of unique identifiers for these nodes, and thus these identifiers would become infinitely large and require infinite memory. Even if you could imagine that in theory, then of course it will take an infinite amount of time for any traversal to visit them all. Both DFS and BFS would keep making progress, but they just visit different nodes.

What is possible however, is to have cycles in your graph. If you follow such a path without further precaution, a DFS will indeed get into an infinite loop.

Changing the algorithm from DFS to BFS may solve this partly, as BFS will still be able to visit all nodes, despite the fact that it will also lose time in traversing cycles.

However, it is much better to deal with the core issue here: the algorithm should stop traversing further down a path when it encounters a node that was already visited before. And then DFS (and BFS) will do the job fine.