Can someone help me optimize my DFS implementation in Python?

def dfs(graph, node):
"""Run DFS through the graph from the starting 
node and return the nodes in order of finishing time.
"""
stack = [[node, True]]
while True in [x[1] for x in stack]:
    i = 0
    for x in xrange(len(stack)):
        if stack[x][1] == True:
            i = x
            break
    stack[i][1] = False
    stack = [[x, True] for x in graph[stack[i][0]] \
                 if (([x, True] not in stack) and ([x, False] not in stack))] + stack
return [x[0] for x in stack]

Input: Graph as adjacency list Eg: {1:[2, 3], 2:[1], 3:[]}

Node is an integer value from where depth first search begins Eg: 1

Output: The list of nodes in order of their finishing times.

Eg: [3, 2, 1]

For large graphs, the above code is taking too long to execute. Is there a better way to do this?

Edit: I could do better time by implementing the following code. Is it possible to do even better?

def dfs(graph, node):
"""Run DFS through the graph from the starting 
node and return the nodes in order of finishing time.
"""
seen = defaultdict(bool)
stack = [node]

while True:
    flag = True
    for x in stack:
        if not seen[x]:
            stack = [a for a in graph[x] if not seen[a]] + stack
            seen[x] = True
            flag = False
            break
     if flag:
        break
return stack

Edit: I've changed seen and stack variables to sets. But I'm not getting the required performance boost. What am I doing wrong?

def dfs(graph, node):
    """Run DFS through the graph from the starting 
    node and return the nodes in order of finishing time.
    """
    seen = set()
    stack = {node}
    while True:
       flag = True
       for x in stack:
           if x not in seen:
                stack = stack.union(set(graph[x]))
                seen = seen.union({x})
                flag = False
                break
        if flag:
            break
    return list(stack)

def dfs(graph, node):

This isn't a depth first search

"""Run DFS through the graph from the starting 
    node and return the nodes in order of finishing time.
    """
    seen = set()
    stack = {node}

You aren't using this as a stack, don't call it that

while True:
       flag = True

avoid flag variables, they confound code. Also that's a very undescriptive name.

for x in stack:
           if x not in seen:

Seen these are sets, you should be probably use: for x in stack - seen: which should be more efficient

stack = stack.union(set(graph[x]))

Using this approach will make things rather slow, you just keep making stack bigger and bigger.

seen = seen.union({x})

Use seen.add to add things to the set. Using union like this will be much slower

flag = False
                break
        if flag:
            break
    return list(stack)

The set gives you no guarantees as to the order of the elements. I'm guessing that's now what you wanted. As it stands,this will end up giving you all the elements in your graph in a random order.

My approach

def breadth_first_search(graph, start):
    seen = set()
    current = {start}
    history = []

    while current:
         history.extend(current) # record when we found all these elements
         seen.update(current) # add them to the list of elements we've already seen
         neighbours = set() # generate a set of all elements that we can reach from these ones
         for node in current:
             neighbours.update(graph[node])
         current = neighbours - seen # the next round of elements is this one, except those we've already seen

    return history

StackExchange Code Review Q#29374, answer score: 5