breath first search bfs can be used when finding the shortest path from a given source node to a target node in an unweighted graph graph is implemented as dictionary of adjacency lists also source vertex have to be defined upon initialization mapping node to its parent in resulting breadth first tree this function is a helper for running breath first search on this graph g graphgraph g g breathfirstsearch g parent g none c g a c f c b a e a d b this shortest path function returns a string describing the result 1 no path is found the string is a human readable message to indicate this 2 the shortest path is found the string is in the form v1v2v3 vn where v1 is the source vertex and vn is the target vertex if it exists separately g graphgraph g g breathfirstsearch case 1 no path is found g shortestpathfoo traceback most recent call last valueerror no path from vertex g to vertex foo case 2 the path is found g shortestpathd gcabd g shortestpathg g graph is implemented as dictionary of adjacency lists also source vertex have to be defined upon initialization mapping node to its parent in resulting breadth first tree this function is a helper for running breath first search on this graph g graph graph g g breath_first_search g parent g none c g a c f c b a e a d b first in first out queue this shortest path function returns a string describing the result 1 no path is found the string is a human readable message to indicate this 2 the shortest path is found the string is in the form v1 v2 v3 vn where v1 is the source vertex and vn is the target vertex if it exists separately g graph graph g g breath_first_search case 1 no path is found g shortest_path foo traceback most recent call last valueerror no path from vertex g to vertex foo case 2 the path is found g shortest_path d g c a b d g shortest_path g g
from __future__ import annotations

graph = {
    "A": ["B", "C", "E"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
    "D": ["B"],
    "E": ["A", "B", "D"],
    "F": ["C"],
    "G": ["C"],
}


class Graph:
    def __init__(self, graph: dict[str, list[str]], source_vertex: str) -> None:
        
        self.graph = graph
        
        self.parent: dict[str, str | None] = {}
        self.source_vertex = source_vertex

    def breath_first_search(self) -> None:
        
        visited = {self.source_vertex}
        self.parent[self.source_vertex] = None
        queue = [self.source_vertex]  

        while queue:
            vertex = queue.pop(0)
            for adjacent_vertex in self.graph[vertex]:
                if adjacent_vertex not in visited:
                    visited.add(adjacent_vertex)
                    self.parent[adjacent_vertex] = vertex
                    queue.append(adjacent_vertex)

    def shortest_path(self, target_vertex: str) -> str:
        
        if target_vertex == self.source_vertex:
            return self.source_vertex

        target_vertex_parent = self.parent.get(target_vertex)
        if target_vertex_parent is None:
            msg = (
                f"No path from vertex: {self.source_vertex} to vertex: {target_vertex}"
            )
            raise ValueError(msg)

        return self.shortest_path(target_vertex_parent) + f"->{target_vertex}"


if __name__ == "__main__":
    g = Graph(graph, "G")
    g.breath_first_search()
    print(g.shortest_path("D"))
    print(g.shortest_path("G"))
    print(g.shortest_path("Foo"))