Is there a situation possible when breadth first search would not terminate?

Question

Does a situation exist when BFS would not terminate ? (Given that the branching factor b is finite)

Answer 1

Only BFS of an infinite graph and when the search doesn't have a specific, reachable target. (You can certainly have an infinite graph with a finite branching factor. An infinitely tall binary tree would suffice.)

The BFS algorithm by its definition looks at a vertex only once, and it looks at one vertex per iteration. Therefore BFS of a graph with any finite number of vertices must terminate.

If the BFS has a reachable target T, then let P be a path from source to target. If the branching factor is at most b, then after P^b steps the BFS must find T.

Edit

I think in retrospect I see the point of this question. If the BFS is for a specific target node T on an infinitely large directed graph, then the BFS will fail to terminate if the search starts from a node from which T is inaccessible, even if the branching factor is limited. For example, suppose you have any infinitely large DAG. Then any node T that is a predecessor of the search start node is inaccessible, so the BFS will run forever without finding it. NB this can't happen on a connected, undirected graph.