Skip to content

Instantly share code, notes, and snippets.

@vaishaks

vaishaks/dfs.py

Created August 4, 2013 18:08
Show Gist options
  • Save vaishaks/6151254 to your computer and use it in GitHub Desktop.
Save vaishaks/6151254 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
dfs.py
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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment