# Breadth First Search (BFS)

This algorithm is used to search or traverse a tree or graph. It explores all nodes at the current depth before moving on to nodes a the next level. Use this when you think the data you are looking for is close to the starting node, rather than far away from it. If you think it is far away use a depth first search instead.

An iterative approach using a queue to keep track of the nodes to explore is generally used.

Time Complexity: O(V + E) where V is the number of verticies and E is the number of edges.

Space Complexity: O(V)

Assume the following graph:

graph = {

"A": ["B", "C", "D"],

"B": ["A", "D", "E"],

"C": ["A", "F"],

"D": ["B", "D"],

"E": ["B", "F"],

"F": ["C", "E", "G"],

"G": ["F"],

}

A visual depiction of the graph

A collections.deque is used to queue the vertices to search. The code is similar to the iterative implementation of the depth first search algorithm.

def bfs_traversal(graph: Dict, start: str) -> List[str]:

if graph is None or start is None or start not in graph:

return []

result = []

queue = deque()

visited = {}

queue.append(start)

visited[start] = True

while queue:

item = queue.popleft()

for vertex in graph[item]:

if vertex not in visited:

visited[vertex] = True

queue.append(vertex)

result.append(vertex)

return result

def bfs(graph: Dict, start: str, target: str) -> bool:

if graph is None or start is None or target is None or start not in graph:

return False

if start == target:

return True

queue = deque()

visited = {}

queue.append(start)

visited[start] = True

while queue:

item = queue.popleft()

for vertex in graph[item]:

if vertex == target:

return True

if vertex not in visited:

visited[vertex] = True

queue.append(vertex)

return False

Traversal of a tree is similar to a graph except the visited collection is not needed. This is because a tree does not have cycles in it. So, we do not need to keep track of the nodes we have already visited.

class TreeNode(object):

def __init__(self, x):

self.val = x

self.left = None

self.right = None

def bfs_traversal(root: TreeNode) -> List[int]:

if not root:

return []

queue = deque()

queue.append(root)

result = []

while queue:

node = queue.popleft()

if node:

result.append(node.val)

queue.append(node.left)

queue.append(node.right)

return result

Last modified 11mo ago