minte9
LearnRemember





Click to Flip Card

Depth First Search 

Does DFS algorithm use backtracking?
Does DFS use recursion?
Where do DFS starts?

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: 301 days ago