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 then the second level containing D,E,F,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 do illustrate it done from left to 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,B and A,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.
2
Answers
In the definition, BFS doesn’t state any rule regarding which node you should visit first as long as it is in the same level. However, depending on your actual implementation, there will be some order. For example for a binary tree (like in the example you have provided), the implementation of BFS might prefer going left then right, other implementations might do the opposite.
Conclusion: it doesn’t really matter, as long as we are considering the general definition of BFS / DFS. If you find the order of visiting nodes in the same level specified in some book, that’s not BFS, that’s a modified BFS, meaning a specific implementation / variant.
Actually there are many variants for DFS / BFS (like right-first DFS on grids) but as I said, all of them are specific implementations, the general definition doesn’t state the order of nodes in the same level.
Here is another view of the problem:
A BFS is usually implemented by using a queue, a first-in first-out data structure, while
A DFS is usually implemented by using a stack, a first-in last-out data structure.
Therefore, how to choose between nodes with the "same priority" depends on how you put those nodes in the stack/queue. There is no fixed rule about it.