The DFS function simply calls itself recursively for every unvisited child of its argument. We can emulate that behaviour precisely using a stack of iterators. Instead of recursively calling with a node, we'll push an iterator to the node's children onto the iterator stack. When the itera
(graph, start)
| 11 | |
| 12 | |
| 13 | def dfs(graph, start): |
| 14 | """The DFS function simply calls itself recursively for every unvisited child of its argument. We can emulate that |
| 15 | behaviour precisely using a stack of iterators. Instead of recursively calling with a node, we'll push an iterator |
| 16 | to the node's children onto the iterator stack. When the iterator at the top of the stack terminates, we'll pop |
| 17 | it off the stack.""" |
| 18 | explored, stack = set(), [start] |
| 19 | explored.add(start) |
| 20 | while stack: |
| 21 | v = stack.pop() # the only difference from BFS is to pop last element here instead of first one |
| 22 | for w in graph[v]: |
| 23 | if w not in explored: |
| 24 | explored.add(w) |
| 25 | stack.append(w) |
| 26 | return explored |
| 27 | |
| 28 | |
| 29 | G = {'A': ['B', 'C'], |