usrbinpython omkar pathak from future import annotations from queue import queue class graph def initself none self vertices dictint listint def printgraphself none for i in self vertices printi joinstrj for j in self verticesi def addedgeself fromvertex int tovertex int none if fromvertex in self vertices self verticesfromvertex appendtovertex else self verticesfromvertex tovertex def bfsself startvertex int setint initialize set for storing already visited vertices visited set create a first in first out queue to store all the vertices for bfs queue queue queue mark the source node as visited and enqueue it visited addstartvertex queue putstartvertex while not queue empty vertex queue get loop through all adjacent vertex and enqueue it if not yet visited for adjacentvertex in self verticesvertex if adjacentvertex not in visited queue putadjacentvertex visited addadjacentvertex return visited if name main from doctest import testmod testmodverbosetrue g graph g addedge0 1 g addedge0 2 g addedge1 2 g addedge2 0 g addedge2 3 g addedge3 3 g printgraph 0 1 2 1 2 2 0 3 3 3 assert sortedg bfs2 0 1 2 3 usr bin python omkar pathak prints adjacency list representation of graaph g graph g print_graph g add_edge 0 1 g print_graph 0 1 adding the edge between two vertices g graph g print_graph g add_edge 0 1 g print_graph 0 1 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 initialize set for storing already visited vertices create a first in first out queue to store all the vertices for bfs mark the source node as visited and enqueue it loop through all adjacent vertex and enqueue it if not yet visited 0 1 2 1 2 2 0 3 3 3
from __future__ import annotations

from queue import Queue


class Graph:
    def __init__(self) -> None:
        self.vertices: dict[int, list[int]] = {}

    def print_graph(self) -> None:
        
        for i in self.vertices:
            print(i, " : ", " -> ".join([str(j) for j in self.vertices[i]]))

    def add_edge(self, from_vertex: int, to_vertex: int) -> None:
        
        if from_vertex in self.vertices:
            self.vertices[from_vertex].append(to_vertex)
        else:
            self.vertices[from_vertex] = [to_vertex]

    def bfs(self, start_vertex: int) -> set[int]:
        
        
        visited = set()

        
        queue: Queue = Queue()

        
        visited.add(start_vertex)
        queue.put(start_vertex)

        while not queue.empty():
            vertex = queue.get()

            
            for adjacent_vertex in self.vertices[vertex]:
                if adjacent_vertex not in visited:
                    queue.put(adjacent_vertex)
                    visited.add(adjacent_vertex)
        return visited


if __name__ == "__main__":
    from doctest import testmod

    testmod(verbose=True)

    g = Graph()
    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)

    g.print_graph()
    
    
    
    

    assert sorted(g.bfs(2)) == [0, 1, 2, 3]