minte9

LearnRemember / ALGORITHMS

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