ā£

**implementation**for BFS

Given an adjacency list [`self.graph = defaultdict(list)`

],

$m \times n$ Adjacency Matrix [`self.graph = matrix`

],

Implement **BFS** (iteratively), and give its run time

**Search**:

- Initialize a visited
`array/map/matrix/table`

and`queue`

with source node - For all vertices in graph, do BFS on unvisited vertices while maintaining record of visited graph

**BFS:**

`Pop`

$v$ from queue and mark vertex $v$ as`visited`

, if not already visited- Do operations (such as
`print`

or`compare`

) - For $\forall$ edges of vertex, on unvisited neighbors

```
class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graphdef addEdge(self,u,v):
self.graph[u].append(v)
# function to print a BFS of graph
def BFS(self, v):
V = self.graph
# Mark all the vertices as not visited
visited = [False] * (len(V))
# Create a queue for BFS
queue = []
# Mark the source node as
# visited and enqueue it
queue.append(v)
visited[v] = True
while queue:
# Dequeue a vertex from
# queue and print it
s = queue.pop(0)
print (s, end = " ") # additional logic here!
# Get all adjacent vertices of the
# dequeued vertex s. If a adjacent
# has not been visited, then mark it
# visited and enqueue it
neighbors = self.graph[n]
for n in neighbors:
if not visited[n]:
queue.append(n)
visited[v] = True
```

```
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def BFS(self, v):
V = self.graph
visited = [False] * (len(V))
queue = []
queue.append(v)
visited[v] = True
while queue:
s = queue.pop(0)
print (s, end = " ")
# additional logic here!
neighbors = self.graph[n]
for n in neighbors:
if not visited[n]:
queue.append(n)
visited[v] = True
```

https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/

ā£

**applications**of BFS?

Shortest path

Finding the minimum spanning tree

Level order tree traversal

ā£

**space complexity**of BFS

$O(|V|)$

ā£

**runtime**of BFS

$O(|V|+|E|)$

ā£

ā£

It visits all reachable nodes from v in breadth first order.