BFS

class BFS:
    def __init__(self, graph: Graph, source: int):
        self.marked = [False] * graph.v
        self.edge_to = [i for i in range(graph.v)]
        self.dist_to = [-1] * graph.v
        self.graph = graph
        self.source = source
        self.__validate_v(source)
        self.__bfs(graph, source)

    def __validate_v(self, v):
        if v < 0 or v >= self.graph.v:
            raise Exception("{} illegal".format(v))

    def __bfs(self, graph, v):
        q = [v]
        self.marked[v] = True
        self.dist_to[v] = 0

        while len(q) != 0:
            w = q.pop()
            for a in graph.get_adj(w):
                if not self.marked[a]:
                    self.marked[a] = True
                    self.edge_to[a] = w
                    self.dist_to[a] = self.dist_to[w] + 1
                    q.append(a)

    def has_path_to(self, v):
        self.__validate_v(v)
        return self.marked[v]

    def path_to(self, v):
        self.__validate_v(v)
        if not self.has_path_to(v):
            return None
        s = []
        x = v
        while self.dist_to[x] != 0:
            s.append(x)
            x = self.edge_to[x]
        s.append(x)
        return s