How to implement Breadth First Search algorithm in Python
By Abhilash BandlaThis Python tutorial helps you to understand what is the Breadth First Search algorithm and how Python implements BFS.
Algorithm for BFS
BFS is one of the traversing algorithm used in graphs. This algorithm is implemented using a queue data structure. In this algorithm, the main focus is on the vertices of the graph. Select a starting node or vertex at first, mark the starting node or vertex as visited and store it in a queue. Then visit the vertices or nodes which are adjacent to the starting node, mark them as visited and store these vertices or nodes in a queue. Repeat this process until all the nodes or vertices are completely visited.
Advantages of BFS
- It can be useful in order to find whether the graph has connected components or not.
- It always finds or returns the shortest path if there is more than one path between two vertices.
Disadvantages of BFS
- The execution time of this algorithm is very slow because the time complexity of this algorithm is exponential.
- This algorithm is not useful when large graphs are used.
Implementation of BFS in Python ( Breadth First Search )
Source Code: BFS in Python
graph = {'A': ['B', 'C', 'E'],
'B': ['A','D', 'E'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'E': ['A', 'B','D'],
'F': ['C'],
'G': ['C']}
def bfs(graph, initial):
visited = []
queue = [initial]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbours = graph[node]
for neighbour in neighbours:
queue.append(neighbour)
return visited
print(bfs(graph,'A'))Explanation:
- Create a graph.
- Initialize a starting node.
- Send the graph and initial node as parameters to the bfs function.
- Mark the initial node as visited and push it into the queue.
- Explore the initial node and add its neighbours to the queue and remove the initial node from the queue.
- Check if the neighbours node of a neighbouring node is already visited.
- If not, visit the neighbouring node neighbours and mark them as visited.
- Repeat this process until all the nodes in a graph are visited and the queue becomes empty.
Output:
['A', 'B', 'C', 'E', 'D', 'F', 'G']
You can also read,
- How to implement Depth First Search algorithm in Python
- How to implement a Queue data structure in Python
graph=
{2: [3, 7, 8, 6],
3: [4, 8],
4: [5],
5: [],
6: [4, 10, 5, 3],
7: [6, 8, 3, 10, 4],
8: [10, 11],
9: [8, 11, 10, 7],
10: [],
11: [10],
12: [11, 22],
13: [10, 18, 11, 12],
14: [5, 13, 15, 6, 10, 18, 16],
15: [13, 5, 10, 18, 17],
16: [15, 17, 18],
17: [18, 21, 26],
18: [21, 22],
19: [12, 18, 13, 11, 22, 21],
21: [22],
22: [],
23: [22, 24, 30, 35],
24: [22, 21],
25: [24, 29, 26, 21, 28, 22, 30],
26: [21, 28, 29],
27: [31, 28, 32],
28: [32, 33],
29: [28, 24, 33, 30, 32],
30: [24, 35, 36, 33],
31: [32, 39, 28],
32: [39],
33: [32],
34: [30, 33, 36, 29, 24, 35],
35: [153],
36: [46, 35, 33],
37: [36, 43, 33, 46, 50],
38: [33, 37, 43, 32],
39: [40],
40: [],
41: [40, 52, 43, 39, 51],
42: [41, 43, 38, 32, 39],
43: [],
44: [37, 50, 45, 43, 49, 38, 46],
45: [50, 48, 46, 37, 62, 47],
46: [],
47: [152, 48, 46],
48: [],
49: [45, 62, 50, 48, 60, 61],
50: [43],
51: [58, 52, 50, 43],
52: [57],
53: [40, 52, 54, 41],
54: [57, 52],
55: [75],
56: [54, 55, 57, 73, 75],
57: [],
58: [52, 57],
59: [57, 58, 71, 73, 67],
60: [50, 61, 51, 58],
61: [62, 50, 68],
62: [48],
63: [64, 62, 149, 48, 150],
64: [150, 105],
65: [61, 63, 62, 68, 64, 67],
66: [65, 84, 68, 63, 64, 83, 85],
67: [61, 60, 68, 70],
68: [70],
69: [67, 71, 59, 70, 58, 68],
70: [],
71: [73, 70, 74, 58],
72: [70, 74, 81, 71, 82],
73: [],
74: [70, 73, 80, 75],
75: [73],
76: [74, 75, 80],
77: [75, 78, 55, 76],
78: [76, 75, 79, 80],
79: [],
80: [79],
81: [82, 90, 74, 80, 70, 76],
82: [89, 70],
83: [82, 84, 68, 70, 89],
84: [64, 68],
85: [64, 86, 105, 84, 102],
86: [102, 84, 87, 99],
87: [99, 95, 84, 98],
88: [84, 87, 83, 86, 89, 82],
89: [87, 93, 95],
90: [80, 93, 82, 89, 91],
91: [79, 80, 92, 93],
92: [94, 79],
93: [92],
94: [],
95: [93, 94, 99],
96: [94],
97: [96, 98, 107, 108],
98: [95, 99, 96, 101],
99: [],
100: [97, 101, 98, 99, 108, 107],
101: [108, 99, 109],
102: [99, 105, 101],
103: [102, 104, 101, 109, 105],
104: [105, 109],
105: [],
106: [107, 110, 111],
107: [96],
108: [107, 111],
109: [108],
110: [111, 115, 107],
111: [107],
112: [108, 113, 109, 117, 111],
113: [111, 117, 116, 108, 110],
114: [110, 116, 115, 111, 113, 117],
115: [],
116: [117, 115, 124],
117: [111],
118: [109, 112, 119, 117, 120, 113],
119: [120, 109, 158, 104],
120: [124, 125, 158],
121: [122, 129, 115],
122: [115, 116],
123: [116, 128, 127, 122, 124, 117],
124: [117],
125: [124],
126: [125, 124, 132],
127: [124, 126, 131, 125],
128: [130, 121, 122, 127, 129, 131],
129: [135, 122, 134],
130: [129, 131, 134, 127, 135],
131: [126, 134, 132],
132: [],
133: [132, 138, 131, 134, 137, 130],
134: [135],
135: [],
136: [135, 137, 143, 134],
137: [134, 141, 146, 143],
138: [137, 139, 132, 141, 134, 140],
139: [140, 132],
140: [],
141: [146, 139, 140],
142: [136, 137, 143, 146, 141, 134, 144],
143: [144],
144: [],
145: [144],
146: [144, 143, 140, 145],
147: [140, 145, 146, 141, 144],
148: [147, 140, 145],
149: [150, 152, 48, 151],
150: [105, 151],
151: [157],
152: [151, 48, 154],
153: [163, 154, 46],
154: [163],
155: [152, 151, 154, 156, 161],
156: [161, 151, 172, 157],
157: [158],
158: [],
159: [157, 156, 172, 173],
160: [156, 159, 172, 161, 173, 171],
161: [],
162: [154, 155, 161, 156],
163: [],
164: [166, 162, 167, 165, 161],
165: [179, 161],
166: [165, 167, 180, 170, 179],
167: [170, 163, 165],
168: [170, 169, 181, 183],
169: [],
170: [],
171: [172, 165, 179, 161],
172: [161, 173, 165],
173: [],
175: [],
176: [173, 175, 191],
177: [178, 189, 171, 173, 176, 172],
178: [171, 188, 179, 189, 193],
179: [],
180: [181, 179, 165, 185],
181: [170, 185],
182: [168, 183, 181, 169, 170],
183: [169],
184: [182, 222, 185, 181, 183, 221],
185: [],
186: [180, 185, 187, 179, 181, 188],
187: [220, 188, 185, 218, 221],
188: [179],
189: [176, 193],
190: [189, 207, 191, 176, 175, 206],
191: [175],
192: [205, 206, 191, 204],
193: [188],
194: [183, 195, 169, 223],
195: [196, 223],
196: [],
197: [196, 225],
198: [197, 225, 239],
199: [239, 200],
200: [],
202: [],
203: [202, 204, 211],
204: [209],
205: [204, 209, 206],
206: [191, 209],
207: [193, 208, 206, 217, 189],
208: [206, 209, 217, 205, 212],
209: [212],
210: [203, 204, 209, 211, 212, 202, 205],
211: [202, 212],
212: [],
213: [234, 214, 235, 211, 212],
214: [212],
215: [208, 216, 217, 209, 212, 214],
216: [214, 229, 219, 217, 235],
217: [193],
218: [188, 193, 217, 228],
219: [217, 218, 228],
220: [218, 228, 221, 185, 219],
221: [185],
222: [185, 221, 223],
223: [183, 196],
224: [223, 226, 225, 195, 196, 198, 231],
225: [],
226: [222, 223, 225],
227: [221, 226, 231, 228, 222],
228: [221, 237],
229: [219, 228, 237, 214, 217],
230: [227, 228, 237, 231, 232, 229],
231: [225, 226, 237],
232: [231, 237, 239, 225, 227],
233: [232, 239, 237, 199, 231],
234: [235, 214, 200],
235: [237, 214],
236: [229, 235, 237, 214, 216, 219],
237: [],
238: [199, 200, 233, 239, 234],
239: [225]}
This is my graph and when I impliment this code on my graph then I got this error : Traceback (most recent call last):
File “C:\Users\raoshab\AppData\Local\Temp/ipykernel_19944/3364066523.py”, line 20, in
bfs(visited, graph, ‘2’)
File “C:\Users\raoshab\AppData\Local\Temp/ipykernel_19944/3364066523.py”, line 13, in bfs
for u in graph[m]:
KeyError: ‘2’
Please help me.
The numbers/letters in the dictionary need to be inside two quotation marks, i.e.’ ‘. I hope this helps.