>>> bfs({1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [8], 6: [], 7: [], 8: []}, 1) 1 2 3 4 5 6 7 8
(g, s)
| 112 | |
| 113 | |
| 114 | def bfs(g, s): |
| 115 | """ |
| 116 | >>> bfs({1: [2, 3], 2: [4, 5], 3: [6, 7], 4: [], 5: [8], 6: [], 7: [], 8: []}, 1) |
| 117 | 1 |
| 118 | 2 |
| 119 | 3 |
| 120 | 4 |
| 121 | 5 |
| 122 | 6 |
| 123 | 7 |
| 124 | 8 |
| 125 | """ |
| 126 | vis, q = {s}, deque([s]) |
| 127 | print(s) |
| 128 | while q: |
| 129 | u = q.popleft() |
| 130 | for v in g[u]: |
| 131 | if v not in vis: |
| 132 | vis.add(v) |
| 133 | q.append(v) |
| 134 | print(v) |
| 135 | |
| 136 | |
| 137 | """ |