Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple depth-first searcher in Python 2.7
'''
Depth-first searcher
Tree:
a
/ \
b c
/|\ \
d e f g
|
h
'''
tree = {
'a': ['b', 'c'],
'b': ['d', 'e', 'f'],
'c': ['g'],
'g': ['h'],
}
# Depth first search with stack
def dfs(tree, target, start):
stack = [start]
visited = set()
while stack:
if stack[-1] == target:
return target
visited.add(stack[-1])
children = tree[stack[-1]] if stack[-1] in tree else []
new_child = None
for child in children:
if child not in visited:
new_child = child
break
if new_child:
stack.append(new_child)
else:
stack.pop(-1)
return None
start = 'a'
test_set = ['a', 'b', 'c', 'f', 'g', 's']
for t in test_set:
print "DFS searching", t, ':', dfs(tree, t, start)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.