# minte9 LearnRemember

### 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

if self not in vertex.adjacent_vertices: # mutual

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')

def dfs_traverse(vertex, visited=[]):
visited.append(vertex.value)

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)

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