- Notifications
You must be signed in to change notification settings - Fork 46.7k
/
Copy pathbreadth_first_search_shortest_path.py
90 lines (76 loc) · 2.95 KB
/
breadth_first_search_shortest_path.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
"""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.
"""
from __future__ importannotations
graph= {
"A": ["B", "C", "E"],
"B": ["A", "D", "E"],
"C": ["A", "F", "G"],
"D": ["B"],
"E": ["A", "B", "D"],
"F": ["C"],
"G": ["C"],
}
classGraph:
def__init__(self, graph: dict[str, list[str]], source_vertex: str) ->None:
"""
Graph is implemented as dictionary of adjacency lists. Also,
Source vertex have to be defined upon initialization.
"""
self.graph=graph
# mapping node to its parent in resulting breadth first tree
self.parent: dict[str, str|None] = {}
self.source_vertex=source_vertex
defbreath_first_search(self) ->None:
"""
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'}
"""
visited= {self.source_vertex}
self.parent[self.source_vertex] =None
queue= [self.source_vertex] # first in first out queue
whilequeue:
vertex=queue.pop(0)
foradjacent_vertexinself.graph[vertex]:
ifadjacent_vertexnotinvisited:
visited.add(adjacent_vertex)
self.parent[adjacent_vertex] =vertex
queue.append(adjacent_vertex)
defshortest_path(self, 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'
"""
iftarget_vertex==self.source_vertex:
returnself.source_vertex
target_vertex_parent=self.parent.get(target_vertex)
iftarget_vertex_parentisNone:
msg= (
f"No path from vertex: {self.source_vertex} to vertex: {target_vertex}"
)
raiseValueError(msg)
returnself.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"))