-
-
Save monkey-codes/6c2b07d1608b394964db1fa51d7a48d5 to your computer and use it in GitHub Desktop.
Simple breadth first search on a graph
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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