-
Notifications
You must be signed in to change notification settings - Fork 1
/
bfs.py
77 lines (65 loc) · 2.23 KB
/
bfs.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
from queue import Queue
romaniaMap = {
'Arad': ['Sibiu', 'Zerind', 'Timisoara'],
'Zerind': ['Arad', 'Oradea'],
'Oradea': ['Zerind', 'Sibiu'],
'Sibiu': ['Arad', 'Oradea', 'Fagaras', 'Rimnicu'],
'Timisoara': ['Arad', 'Lugoj'],
'Lugoj': ['Timisoara', 'Mehadia'],
'Mehadia': ['Lugoj', 'Drobeta'],
'Drobeta': ['Mehadia', 'Craiova'],
'Craiova': ['Drobeta', 'Rimnicu', 'Pitesti'],
'Rimnicu': ['Sibiu', 'Craiova', 'Pitesti'],
'Fagaras': ['Sibiu', 'Bucharest'],
'Pitesti': ['Rimnicu', 'Craiova', 'Bucharest'],
'Bucharest': ['Fagaras', 'Pitesti', 'Giurgiu', 'Urziceni'],
'Giurgiu': ['Bucharest'],
'Urziceni': ['Bucharest', 'Vaslui', 'Hirsova'],
'Hirsova': ['Urziceni', 'Eforie'],
'Eforie': ['Hirsova'],
'Vaslui': ['Iasi', 'Urziceni'],
'Iasi': ['Vaslui', 'Neamt'],
'Neamt': ['Iasi']
}
def bfs(startingNode, destinationNode):
# For keeping track of what we have visited
visited = {}
# keep track of distance
distance = {}
# parent node of specific graph
parent = {}
bfs_traversal_output = []
# BFS is queue based so using 'Queue' from python built-in
queue = Queue()
# travelling the cities in map
for city in romaniaMap.keys():
# since intially no city is visited so there will be nothing in visited list
visited[city] = False
parent[city] = None
distance[city] = -1
# starting from 'Arad'
startingCity = startingNode
visited[startingCity] = True
distance[startingCity] = 0
queue.put(startingCity)
while not queue.empty():
u = queue.get() # first element of the queue, here it will be 'arad'
bfs_traversal_output.append(u)
# explore the adjust cities adj to 'arad'
for v in romaniaMap[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
distance[v] = distance[u] + 1
queue.put(v)
# reaching our destination city i.e 'bucharest'
g = destinationNode
path = []
while g is not None:
path.append(g)
g = parent[g]
path.reverse()
# printing the path to our destination city
print(path)
# Starting City & Destination City
bfs('Arad', 'Bucharest')