Why is Depth-First Search said to suffer from infinite loops?
I have read about DFS and BFS many times but I have this doubt lingering my mind since long. In a lot of articles it is mentioned that DFS can get stuck in infinite loops.
As far as I know, this limitation can easily be removed by keeping track of the visited nodes. In fact, in all the books that I have read, this little check is a part of DFS.
So why are 'infinite loops' mentioned as a disadvantage of DFS? Is it just because the original DFS algorithm did not have this check for visited nodes? Please explain.
Answer
(1) In graph search algorithms [used frequently on AI], DFS's main advantage is space efficiency. It is its main advantage on BFS. However, if you keep track of visited nodes, you lose this advantage, since you need to store all visited nodes in memory. Don't forget the size of visited nodes increases drastically over time, and for very large/infinite graphs - might not fit in memory.
(2) Sometimes DFS can be in an infinite branch [in infinite graphs]. An infinite branch is a branch that does not end [always has "more sons"], and also does not get you to your target node, so for DFS, you might keep expanding this branch inifinitely, and 'miss' the good branch, that leads to the target node.
Bonus:
You can overcome this flaw in DFS, while maintaining relatively small memory size by using a combination of DFS and BFS: Iterative Deepening DFS