Depth First Search
Chapter Thirteen
Syllabus topic Module 1, "DFS"
Pages 62 to 66 of 591
In one line
Depth first search follows one branch all the way to the bottom before trying anything else, which uses almost no memory and can go badly wrong.
In the wording a student can write in an examination: depth first search always expands the deepest unexpanded node. The frontier is a last in, first out stack. It is not optimal, and in tree search it is not complete on an infinite state space or one with cycles. Its time complexity is O(b**m) where m is the maximum depth, but its space complexity is only O(b*m), which is linear rather than exponential and is the reason it is used at all.
The one line of difference
Breadth first search takes the oldest path off the frontier. Depth first search takes the newest. Swapping a queue for a stack is the entire difference between the two algorithms, and it changes every one of their four properties.
A node's children are the newest things on the frontier the moment they are generated, so a stack serves one of them next. The search therefore goes down, and keeps going down, until it can go no further; only then does it come back up to the most recent untried alternative. That is called backtracking.
The algorithm
frontier = a STACK holding the path [start]; visited = {}
loop:
if frontier is empty: return failure
path = frontier.pop() <- the NEWEST path: the whole difference
node = last state of path; if node in visited: continue
add node to visited
if node is a goal: return path
push path + [child] for every child of node not in visitedThe recursive form is the same algorithm and is how it is usually written, because the machine's own call stack then IS the frontier:
def depth_first(node, goal, seen):
if node is a goal: return [node]
seen.add(node)
for child of node not in seen:
found = depth_first(child, goal, seen)
if found: return [node] + found
return failureThe recursive form's memory is the call stack, and it is the same O(b*m). On a deep space it will exhaust the interpreter's recursion limit before it exhausts memory, which is a real failure mode and not a theoretical one.
It running on the district map
ROAD = {
"Amba": {"Bori": 8, "Chinch": 7, "Erandol": 33},
"Bori": {"Amba": 8, "Chinch": 12, "Devi": 5},
"Chinch": {"Amba": 7, "Bori": 12, "Erandol": 7, "Gokul": 13},
"Devi": {"Bori": 5, "Fanas": 7, "Hivra": 9},
"Erandol": {"Amba": 33, "Chinch": 7, "Fanas": 9, "Gokul": 6},
"Fanas": {"Devi": 7, "Erandol": 9, "Hivra": 2, "Jalna": 5},
"Gokul": {"Chinch": 13, "Erandol": 6, "Jalna": 6},
"Hivra": {"Devi": 9, "Fanas": 2, "Jalna": 16},
"Jalna": {"Fanas": 5, "Gokul": 6, "Hivra": 16},
}
def km(path):
return sum(ROAD[path[i]][path[i + 1]] for i in range(len(path) - 1))
def depth_first_search(start, goal):
frontier = [[start]] # a STACK of paths
visited = set()
step = 0
while frontier:
path = frontier.pop() # newest first: that is the stack
node = path[-1]
if node in visited:
continue
visited.add(node)
step += 1
print("%2d expand %-8s depth %d path %s"
% (step, node, len(path) - 1, " > ".join(path)))
if node == goal:
return path
for child in sorted(ROAD[node], reverse=True):
if child not in visited:
frontier.append(path + [child])
return None
route = depth_first_search("Amba", "Jalna")
print()
print("route found:", " > ".join(route))
print("hops:", len(route) - 1, " cost:", km(route), "km")Depth First Search
1 expand Amba depth 0 path Amba
2 expand Bori depth 1 path Amba > Bori
3 expand Chinch depth 2 path Amba > Bori > Chinch
4 expand Erandol depth 3 path Amba > Bori > Chinch > Erandol
5 expand Fanas depth 4 path Amba > Bori > Chinch > Erandol > Fanas
6 expand Devi depth 5 path Amba > Bori > Chinch > Erandol > Fanas > Devi
7 expand Hivra depth 6 path Amba > Bori > Chinch > Erandol > Fanas > Devi > Hivra
8 expand Jalna depth 7 path Amba > Bori > Chinch > Erandol > Fanas > Devi > Hivra > Jalna
route found: Amba > Bori > Chinch > Erandol > Fanas > Devi > Hivra > Jalna
hops: 7 cost: 68 kmRead the depth column: 0, 1, 2, 3, 4, 5, 6, 7. It never goes back up once, because on this small map every town it reaches has an unvisited neighbour. That is depth first search in its purest form.
The route it returns is seven hops and 68 km. The cheapest is 25 km and the fewest hops is three. It went from Fanas to Devi to Hivra to Jalna when it was standing next to Jalna at Fanas with a 5 km road to it: at step 5 the stack's newest entry was the Devi branch, so that is where it went.
It also passed within one road of the goal at step 5 and did not notice, because the goal test is applied when a node is expanded and Jalna was not expanded until step 8. That is not a bug to be fixed by testing children early. Testing early in depth first search would make it return the first goal it stumbles on, which is still not optimal and would hide nothing.
Why depth first search is in the syllabus at all
The answer is one column of the table, and it is worth being precise about.
Depth First Search
Space is O(b*m), linear. The frontier holds only the untried siblings along the current path: at most b siblings at each of at most m levels. At a branching factor of 10 and a depth of 12 that is about 120 nodes, against breadth first search's thousand million million.
That is the whole case, and it is a strong one. Depth first search can run on a problem breadth first search cannot be started on. Every good uninformed algorithm in this row is a way of keeping that memory behaviour while recovering the properties depth first search throws away, and Iterative Deepening Search is the one that succeeds.
The two failures, exactly stated
It is not optimal. It returns the first goal on the first branch that reaches one, and that branch has nothing to recommend it. Here: 68 km against 25.
It is not complete in tree search. Two separate cases, and both should be named.
- On an infinite space it can descend forever down a branch with no goal on it, and the answer sitting one step to the right is never examined.
- On a finite space with cycles it can loop: Amba to Bori to Amba to Bori, forever. The run above avoided this only because of the
visitedset.
So there are really three algorithms wearing this name, and papers distinguish them:
| Keeps | Complete | Space | |
|---|---|---|---|
| Tree search depth first | nothing | no | O(b*m) |
| Depth first with cycle checking on the current path | the current path | on a finite space, yes | O(b*m) |
| Graph search depth first | every visited state | on a finite space, yes | O number of states |
The program above is the third. It is complete on this map, and its space is no longer linear, which costs the algorithm its one advantage. The middle row is the useful compromise and is exactly what Iterative Deepening Search uses.
Depth limited search
The obvious patch for the infinite branch is to refuse to go below a fixed depth L. That is depth limited search, and it has its own properties:
- Complete only if
Lis at leastd. Set the limit too low and it reports failure when a solution exists. - Not optimal, for the same reason as before.
- Time
O(b**L), spaceO(b*L).
Its return value has three cases, not two, and the third is the one that matters: solution, failure (no solution exists), or cutoff (none was found within the limit, and one may exist deeper). A program that merges cutoff with failure will report that a solvable problem has no answer.
Depth limited search is the building block of the next chapter, which removes the need to guess L at all.
Depth First Search
Distinctions
| Depth first | Breadth first | |
|---|---|---|
| Frontier | stack, newest first | queue, oldest first |
| Finds | the first goal down one branch | the shallowest goal |
| Optimal | no | in steps |
| Complete, tree search | no | yes if b finite |
| Space | O(b*m) linear | O(b**d) exponential |
| On the district map | 68 km, 7 hops, 8 expansions | 26 km, 3 hops, 6 expansions |
| Failure | Cutoff | |
|---|---|---|
| Means | there is no solution | none was found within the limit |
| What to do | stop | try a deeper limit |
| Merging them | reports solvable problems unsolvable |
What it does not mean
Depth first search is not faster than breadth first search. Its time complexity is worse, O(bm) against O(bd), because m can be much larger than d. Its advantage is memory only.
It is not complete just because it terminated once. Termination on one problem says nothing. In tree search on a cyclic or infinite space it is not complete, and that is a property of the algorithm.
The visited set is not part of plain depth first search. Adding it makes the algorithm complete on a finite space and destroys its linear space, which is the trade-off to state, not to hide.
Backtracking is not a separate algorithm. It is what depth first search does when a branch is exhausted.
A bad answer is not a bug here. Depth first search never promised a good one. Judging it by the route it returned is judging it against a promise it did not make.
Quick revision
- Depth first search: expand the deepest unexpanded node. Frontier is a LIFO stack. Recursively, the call stack is the frontier.
- Not optimal. Not complete in tree search: it can descend an infinite branch forever, and it can cycle on a finite graph.
- Time
O(bm), spaceO(b*m). The linear space is its entire justification**: about 120 nodes where breadth first search needs a thousand million million. - Three variants: tree search (incomplete, linear space), cycle checking on the current path (complete on a finite space, still linear), graph search with a visited set (complete, space proportional to the number of states).
- On the standing map: 8 expansions, seven hops, 68 km, passing one road from the goal at step 5 without noticing, because the goal test is applied on expansion.
- Depth limited search: refuse to go below
L. Complete only ifLis at least d, not optimal, timeO(bL), spaceO(b*L). Its answer has three cases: solution, failure, cutoff**.
Test yourself
1. Define depth first search and give its frontier data structure. It always expands the deepest unexpanded node. The frontier is a last in, first out stack; in the recursive form the machine's own call stack serves as the frontier.
Depth First Search
2. State its four properties with the conditions. Not optimal. Not complete in tree search, either on an infinite space or on a finite space with cycles. Time O(b**m) where m is the maximum depth. Space O(b*m), which is linear.
3. Why is it in the syllabus at all, given that it is neither complete nor optimal? Because of its memory. It holds only the untried siblings along one path, at most b at each of m levels, so it can be run on problems where breadth first search cannot even be started.
4. In this chapter's run the search stood at Fanas, one 5 km road from the goal, and went to Devi instead. Explain. The goal test is applied when a node is expanded, not when it is generated, and the stack served the most recently pushed branch, which was Devi. Jalna was not expanded until step 8.
5. Give the three variants of depth first search and the property each has. Tree search, which keeps nothing and is not complete but uses linear space. Cycle checking against the current path, which is complete on a finite space and still uses linear space. Graph search with a set of every visited state, which is complete but uses space proportional to the number of states.
6. What are the three possible results of depth limited search, and why does the third matter? A solution, failure, or cutoff. Cutoff means no solution was found within the limit although one may exist deeper. Merging cutoff with failure makes the program report that a solvable problem has no solution.
7. A student claims depth first search is faster than breadth first search because it goes straight down. Correct them. Speed is measured in nodes generated. Depth first search is O(bm) and breadth first search is O(bd), and m can be far larger than d, so depth first search is generally slower. Its advantage is space, not time.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.