| 8 | |
| 9 | |
| 10 | class Graph: |
| 11 | def __init__(self) -> None: |
| 12 | self.vertices: dict[int, list[int]] = {} |
| 13 | |
| 14 | def print_graph(self) -> None: |
| 15 | """ |
| 16 | prints adjacency list representation of graaph |
| 17 | >>> g = Graph() |
| 18 | >>> g.print_graph() |
| 19 | >>> g.add_edge(0, 1) |
| 20 | >>> g.print_graph() |
| 21 | 0 : 1 |
| 22 | """ |
| 23 | for i in self.vertices: |
| 24 | print(i, " : ", " -> ".join([str(j) for j in self.vertices[i]])) |
| 25 | |
| 26 | def add_edge(self, from_vertex: int, to_vertex: int) -> None: |
| 27 | """ |
| 28 | adding the edge between two vertices |
| 29 | >>> g = Graph() |
| 30 | >>> g.print_graph() |
| 31 | >>> g.add_edge(0, 1) |
| 32 | >>> g.print_graph() |
| 33 | 0 : 1 |
| 34 | """ |
| 35 | if from_vertex in self.vertices: |
| 36 | self.vertices[from_vertex].append(to_vertex) |
| 37 | else: |
| 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]: |
no outgoing calls
no test coverage detected