Table of Contents

Vocabulary

Breadth First Search (BFS)

What Is Breadth First Search?

<aside> 💡 Breadth First Search (BFS) is a graph traversal algorithm that traverse a graph closest to a given starting node. The traversal can also be though of as going through the graph in a level-by-level basis.

</aside>

BFS Algorithm Explanation

<aside> 💡 BFS works by pushing nodes to be visited in a queue. When a node is visted, it is marked as visited and any edges the node has to other nodes are added to the queue.

BFS Algorithm Steps

1. Pushing the starting node onto the queue.
2. Pop the starting node, mark it has visited and mark its children nodes as visited + push the node’s edges (the other nodes it’s connected to) onto the queue.
3. Pop the next node off of the queue and repeat step 2 until there there are no edges. If a node has already been visited, do not push it into the queue!

</aside>

def bfs (graph, node) :
	visited = []
	queue = []
	
	#Add starting node to queues.
	visited.append(node)
	queue.append(node)

  #While the queue isn't empty, pop + print the node.
	while queue:
		s = queue.pop(0)
		print(s, end = " ")
		 
		for n in graph[s]:
			if n not in visited:
					visited.append (n)
					queue.append (n)

Time Complexity

<aside> 💡 The Time Complexity of Breadth First Search is $O(V+E)$. At worst case, we will visit every node and explore every edge.

</aside>