>>> g = Graph() >>> g.add_edge(0, 1) >>> g.add_edge(0, 1) >>> g.add_edge(0, 2) >>> g.add_edge(1, 2) >>> g.add_edge(2, 0) >>> g.add_edge(2, 3) >>> g.add_edge(3, 3) >>> sorted(g.bfs(2)) [0, 1, 2, 3]
(self, start_vertex: int)
| 38 | self.vertices[from_vertex] = [to_vertex] |
| 39 | |
| 40 | def bfs(self, start_vertex: int) -> set[int]: |
| 41 | """ |
| 42 | >>> g = Graph() |
| 43 | >>> g.add_edge(0, 1) |
| 44 | >>> g.add_edge(0, 1) |
| 45 | >>> g.add_edge(0, 2) |
| 46 | >>> g.add_edge(1, 2) |
| 47 | >>> g.add_edge(2, 0) |
| 48 | >>> g.add_edge(2, 3) |
| 49 | >>> g.add_edge(3, 3) |
| 50 | >>> sorted(g.bfs(2)) |
| 51 | [0, 1, 2, 3] |
| 52 | """ |
| 53 | # initialize set for storing already visited vertices |
| 54 | visited = set() |
| 55 | |
| 56 | # create a first in first out queue to store all the vertices for BFS |
| 57 | queue: Queue = Queue() |
| 58 | |
| 59 | # mark the source node as visited and enqueue it |
| 60 | visited.add(start_vertex) |
| 61 | queue.put(start_vertex) |
| 62 | |
| 63 | while not queue.empty(): |
| 64 | vertex = queue.get() |
| 65 | |
| 66 | # loop through all adjacent vertex and enqueue it if not yet visited |
| 67 | for adjacent_vertex in self.vertices[vertex]: |
| 68 | if adjacent_vertex not in visited: |
| 69 | queue.put(adjacent_vertex) |
| 70 | visited.add(adjacent_vertex) |
| 71 | return visited |
| 72 | |
| 73 | |
| 74 | if __name__ == "__main__": |