# BFS – Breadth-first search algorithm

Date: April 24, 2020

Categories: Algorithms

BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph by exploring all the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes. Basically traversing the tree or graph layer by layer.

**Pseudocode**

```
1 procedure BFS(G, start_v) is
2 let Q be a queue
3 label start_v as discovered
4 Q.enqueue(start_v)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as discovered then
11 label w as discovered
12 w.parent := v
13 Q.enqueue(w)
```

Python Implementation

```
class GraphTraversals:
def __init__(self, graph):
self.graph = graph
def __str__(self):
return str(self.graph)
def bfs(self, source):
visited = []
queue = []
# add the initial source
queue.append(source)
visited.append(source)
while len(queue) > 0:
s = queue.pop(0)
node = self.graph[s]
for children in node:
if children not in visited:
visited.append(children)
queue.append(children)
print(visited)
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
g = GraphTraversals(graph)
print(g.bfs('A'))
```