Menu
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.
598
Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; this avoids infinite loops in the finite state spaces but does not avoid the proliferation of redundant paths.
Depth-first tree search can get stuck in an infinite loop, which is why it is not "complete". Graph search keeps track of the nodes it has already searched, so it can avoid following infinite loops. "Redundant paths" are different paths which lead from the same start node to the same end node.
Depth First Search. The purpose of Depth First Search (DFS), like Breadth First Search, is to visit every node of a graph and collect some sort of information about how that node was discovered.
Complexity of Depth-first Search Depth-first search visits every vertex once and checks every edge in the graph once. Therefore, DFS complexity is O ( V + E ) O(V + E) O(V+E).
a conventional DFS algorithm does track down nodes. A local search algorithm does not track down states and behaves with amnesia. So I think the loop mainly refers to the one an infinite branch(a branch with infinite possible states). In that case, DFS simply goes down and become too focused on one branch.
23
(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
178
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
