Depth First Search
Does DFS algorithm use backtracking? Does DFS use recursion? Where do DFS starts?
![](/lib/images/knowledge_graph.png)
DFS Traversal
The key to any graph search algorithm is keeping track of the visited vertex. Otherwise we can end up in an infinite cycle.
class Vertex:
def __init__(self, name):
self.value = name
self.adjacent_vertices = []
def add(self, vertex):
self.adjacent_vertices.append(vertex)
if self not in vertex.adjacent_vertices: # mutual
vertex.adjacent_vertices.append(self)
return self
a = Vertex('Alice')
b = Vertex('Bob')
c = Vertex('Candy')
d = Vertex('Derek')
e = Vertex('Elaine')
f = Vertex('Fred')
g = Vertex('Gina')
h = Vertex('Helen')
i = Vertex('Irena')
a.add(b).add(c).add(d).add(e)
b.add(f); c.add(h); d.add(e).add(g); e.add(d)
f.add(h)
g.add(i)
h.add(c)
def dfs_traverse(vertex, visited=[]):
visited.append(vertex.value)
for v in vertex.adjacent_vertices:
if v.value in visited:
continue
dfs_traverse(v, visited) # recusion
return visited
print([x for x in dfs_traverse(a)])
print([x for x in dfs_traverse(f, visited=[]) ])
"""
['Alice', 'Bob', 'Fred', 'Helen', 'Candy', 'Derek', 'Elaine', 'Gina', 'Irena']
['Fred', 'Bob', 'Alice', 'Candy', 'Helen', 'Derek', 'Elaine', 'Gina', 'Irena']
"""
Search One
We can actually search for a particular vertex.
def dfs(vertex, search_value, visited=[]):
# Return the original vertex if it happens to be the one we are searching for:
if vertex.value == search_value:
return vertex
visited.append(vertex.value)
for v in vertex.adjacent_vertices:
if v.value in visited:
continue
# Return the adjacent value if is the one we are searcing for:
if v.value == search_value:
return v
search_vertex = dfs(v, search_value, visited) # recusion
if search_vertex != None:
return search_vertex
return None
print('Helen =', dfs(a, 'Helen'))
print('Derek =', dfs(a, 'Derek'))
print('Unknown =', dfs(a, 'Unknown'))
"""
Helen = <__main__.Vertex object at 0x0000017C45AEAAF0>
Derek = <__main__.Vertex object at 0x0000017C45A9EC40>
Unknown = None
"""
Last update: 344 days ago