Skip to content

Instantly share code, notes, and snippets.

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

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

Select an option

Save monkey-codes/6c2b07d1608b394964db1fa51d7a48d5 to your computer and use it in GitHub Desktop.
Simple breadth first search on a graph
def bfs(self, start_node_num):
"""An iterative implementation of Breadth First Search
iterating through a node's edges."""
node = self.find_node(start_node_num)
self._clear_visited()
ret_list = []
# Your code here
queue = [node]
node.visited = True
def enqueue(n, q=queue):
n.visited = True
q.append(n)
def unvisited_outgoing_edge(n, e):
return ((e.node_from.value == n.value) and
(not e.node_to.visited))
while queue:
node = queue.pop(0)
ret_list.append(node.value)
for e in node.edges:
if unvisited_outgoing_edge(node, e):
enqueue(e.node_to)
return ret_list
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment