graphs.breadth_first_search_shortest_path

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.

Attributes

g

graph

Classes

Graph

Module Contents

class graphs.breadth_first_search_shortest_path.Graph(graph: dict[str, list[str]], source_vertex: str)

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’}

shortest_path(target_vertex: str) → str

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’

graph
parent: dict[str, str | None]
source_vertex
graphs.breadth_first_search_shortest_path.g
graphs.breadth_first_search_shortest_path.graph