Click to Flip Card
Graph Traversal / Depth First Search
DFS explores as far as possible before backtracking. Depth First Search uses recursion. The algorithm starts at the root node (selected arbitrary).
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: 59 days ago
