Implementation of breadth first search using queue.Queue. >>> ''.join(breadth_first_search(G, 'A')) 'ABCDEF'
(graph: dict, start: str)
| 30 | |
| 31 | |
| 32 | def breadth_first_search(graph: dict, start: str) -> list[str]: |
| 33 | """ |
| 34 | Implementation of breadth first search using queue.Queue. |
| 35 | |
| 36 | >>> ''.join(breadth_first_search(G, 'A')) |
| 37 | 'ABCDEF' |
| 38 | """ |
| 39 | explored = {start} |
| 40 | result = [start] |
| 41 | queue: Queue = Queue() |
| 42 | queue.put(start) |
| 43 | while not queue.empty(): |
| 44 | v = queue.get() |
| 45 | for w in graph[v]: |
| 46 | if w not in explored: |
| 47 | explored.add(w) |
| 48 | result.append(w) |
| 49 | queue.put(w) |
| 50 | return result |
| 51 | |
| 52 | |
| 53 | def breadth_first_search_with_deque(graph: dict, start: str) -> list[str]: |