Depth First Search

dfs.py

"""
@Author: Sujayyendhiren Ramarao Srinivasamurthi
@Description: My implementation of DFS
"""
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrack( parent , start, end ):
    res = [ end ]
    node = parent[res[-1]]

    while node != start:
        res.append( node )
        node = parent[res[-1]]

    res.append(start)
    res.reverse()

    return res

def dfs(start, end):

    queue = []
    visited = {}
    parent = {}

    node = start
    queue.append(start)

    while queue:

        node = queue.pop(0)

        if( node != end):
            adjNodes = graph.get(node,[])

            for adj in adjNodes:
                if adj not in visited:
                    queue.insert( 0, adj )
                    visited[adj] = adj
                    parent[adj] = node
        else:
            return backtrack( parent, start, end)

if __name__ == '__main__':
    print dfs( '1', '11' )