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.
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.
Traversal
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
Search
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
Tree
Traversal
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
