How do the BFS and DFS search algorithms choose between nodes with the "same priority"?

Question

I am currently taking an Artificial Intelligence course and learning about DFS and BFS.

If we take the following example:

From my understanding, the BFS algorithm will explore the first level containing $B$ and $C$, then the second level containing $D,E,F$ and $G$, etc., till it reaches the last level.

I am lost concerning which node between $B$ and $C$ (for example) will the BFS expand first?

Originally, I thought it is different every time, and, by convention, we choose to illustrate that it's done from the left to the right (so exploring $B$ then $C$), but my professor said that our choice between $B$ and $C$ depends on each case and we choose the "shallowest node first".

In made examples, there isn't a distance factor between $A$ and $B$, and $A$ and $C$, so how could one choose then?

My question is the same concerning DFS where I was told to choose the "deepest node first". I am aware that there are pre-order versions and others, but the book "Artificial Intelligence - A Modern Approach, by Stuart Russel" didn't get into them.

I tried checking the CLRE algorithms book for more help but the expansion is done based on the order in the adjacency list which didn't really help.

Answer 1

BFS and DFS are usually applied to unweighted graphs (or, equivalently, to graphs where the edges have all the same weights). In this case, BFS is optimal, i.e., assuming a finite branching factor, it eventually finds the optimal solution, but it doesn't mean that it takes a short time, in fact, it might well be the opposite, depending on the search space. DFS would not be optimal because it may not terminate if there is an infinite path.

In the case of unweighted graphs, BFS really proceeds level-by-level. In other words, it starts at the root (level $l=0$), then expands (i.e. adds to the FIFO queue) all children of the root (level $l=1$), then it expands all children of the children of the root (level $l=2$), and so on. So, for example, all children at level $l=2$ have a distance of $2$ to the root (if we assume that edges have a weight of $1$).

The order in which you choose nodes at a certain level to add to your FIFO queue is, as far as I know, typically from left-to-right, but you could, in principle, choose them in different ways (e.g. from right-to-left). So, this is a convention. Of course, this choice may affect when (and if, in the case of DFS) you find the solution.

Now, if we applied BFS to a weighted graph, then what happens here? It depends. If you ignore the weights, then it is the usual BFS. If you take into account the weights, it depends on how you take them into account. For example, if you choose to expand (i.e. add to the queue) nodes with the shortest path so far to the root, then this becomes a uniform-cost search (this is explained in the AIMA book, e.g. 3rd edition, section 3.4.2, p. 83).

So, maybe your professor has in mind the uniform-cost search when he's telling you to choose the "shallowest node first", but you need to talk to him, tell him about uniform-cost search, and ask him if that's what he means.

It also seems to me that your original idea of how DFS works is correct. It goes deep, then backtracks (without taking into account weights). If you take into account the weights, I don't know what DFS could turn into.

Answer 2

Either one. The BFS algorithm and DFS algorithm do not specify.

Typically, it's programmed as left-to-right, just because that's the way programmers think about trees. It doesn't have to be.

Note that DFS isn't "deepest node first" either. Imagine that nodes H and I in your tree did not exist; D, J, K, E, B would be a perfectly valid DFS traversal of B, even though J and K are deeper than D. So would B, D, E, J, K even though E is the parent of J and K! DFS says that you look at a node's children before you look at other nodes on the same layer, but it doesn't say you have to look at the node's children before the node itself. In fact there are three well-known variants (pre-order, post-order and in-order) depending on whether you visit each node before, after or in the middle of its children.

Now, if this is for an AI then you probably do care about the order. If this tree represents a game tree, then you probably want to estimate which node is likely to have the best outcome for the AI player, and check that one first. This can be called "best-first search".