Skip to content

Instantly share code, notes, and snippets.

@monkey-codes
Created May 17, 2017 06:29
Show Gist options
  • Select an option

  • Save monkey-codes/7ba30c2c687f90830f70b5a509b75e66 to your computer and use it in GitHub Desktop.

Select an option

Save monkey-codes/7ba30c2c687f90830f70b5a509b75e66 to your computer and use it in GitHub Desktop.
Simple depth first traversal on a graph
def dfs(self, start_node):
"""Recursive implementation
of Depth First Search iterating through a node's edges.
"""
ret_list = [start_node.value]
start_node.visited = True
edges_out = [e for e in start_node.edges
if e.node_to.value != start_node.value]
for edge in edges_out:
if not edge.node_to.visited:
ret_list.extend(self.dfs_helper(edge.node_to))
return ret_list
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment