dfs-non-recursive

g = {1: [2, 3],  2: [4, 5], 3: [6, 7], 6: [7], 7: [9]}
arr = [1]
visited = [1]
while arr:
    n = arr[0]

    if n not in g.keys():
        print arr
        arr.pop(0)
    else:
        allChildVisited = True
        for x in g[n]:
            if x not in visited:
                arr.insert(0, x)                
                visited.append(x)
                allChildVisited = False
                break
        if allChildVisited:
            arr.pop(0)