Skip to content

Instantly share code, notes, and snippets.

@slashvar

slashvar/dfs.py

Created July 22, 2017 18:10
Show Gist options
  • Save slashvar/d4954d04352fc38356f774198e3aa86b to your computer and use it in GitHub Desktop.
Save slashvar/d4954d04352fc38356f774198e3aa86b to your computer and use it in GitHub Desktop.
Download ZIP
A simple DFS example
Raw
dfs.py
import graphviz
g = {
'A': ['B', 'C', 'D', 'F'],
'B': ['C', 'D'],
'D': ['A', 'C'],
'C': [],
'E': ['C', 'G'],
'F': ['A', 'C'],
'G': ['E']
}
def dfs(g, cur, mark, tree):
mark[cur] = True
for succ in g[cur]:
if not mark[succ]:
tree.edge(cur, succ)
dfs(g, succ, mark, tree)
tree = graphviz.Digraph(name='g')
mark = { v : False for v in g.keys() }
dfs(g, 'A', mark, tree)
tree.save(filename='g.dot')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment