Breadth First Search connected graph with start node. Args: graph (list): GRAPH represented by adjacent list, [set(1,2,3), set(...), ...]. start (int): Index of any start vertex.
(graph, start)
| 48 | |
| 49 | |
| 50 | def _graph_bfs_from_node(graph, start): |
| 51 | '''Breadth First Search connected graph with start node. |
| 52 | |
| 53 | Args: |
| 54 | graph (list): GRAPH represented by adjacent list, [set(1,2,3), set(...), ...]. |
| 55 | start (int): Index of any start vertex. |
| 56 | ''' |
| 57 | search_queue = deque() |
| 58 | searched = set() |
| 59 | |
| 60 | search_queue.append(start) |
| 61 | while search_queue: |
| 62 | cur_node = search_queue.popleft() |
| 63 | if cur_node in searched: continue |
| 64 | yield cur_node |
| 65 | searched.add(cur_node) |
| 66 | for node in graph[cur_node]: |
| 67 | search_queue.append(node) |
| 68 | |
| 69 | |
| 70 |