Breath First Search (BFS)

• The Breath First Search (BFS) is another fundamental search algorithm used to explore nodes and edges of a graph.

• It runs with a time complexity of $O(V+E)$ and is often used as a building block in other algorithms.

• The BFS algorithm is particularly useful for one thing: finding the shortest path on unweighted graphs.

• A BFS starts at some arbitrary node of a graph and explores the neighbor nodes first, before moving to the next level neighbors.

  

  • It does this by maintaining a queue of which node it should visit next.

    

  • Add all neighboring nodes to the queue.

  • If there are no more unvisited neighbors, remove the parent node from the queue, and move on to the next element in the queue.

  • When adding a node to the queue, check if it is already in the queue. If not, then add.

  • Do this repeatedly until the queue runs out.

Using a Queue

• The BFS algorithm uses a queue data structure to track which node to visit next.
• Upon reaching a new node the algorithm adds it to the queue to visit it later.
• The queue data structure works just like a real world queue such as a waiting line at a restaurant. People can either enter the waiting line (enqueue) or get seated (dequeue).

Pseudocode

// Global/class scope variables
n = number of nodes in the graph
g = adjacency list representing unweighted graph

// s = start node, e = end node, and 0 <= e, s < n
function bfs(s, e):

	// Do a BFS starting at node s
	prev = solve(s)

	// Return reconstructed path from s -> 2
	return reconstructPath(s, e, prev)

function solve(s):
	q = queue data structure with enqueue and dequeue
	q.enqueue(s)

	visited = [false, ..., false] // size n
	visited[s] = true

	prev = [null, ..., null] // size n
	while !q.isEmpty():
		node = q.dequeue()
		neighbors = g.get(node)

		for (next : neighbors):
			if !visited[next]:
				q.enqueue(next)
				visited[next] = true
				prev[next] = node

	return prev

function reconstructPath(s, e, prev):
	// Reconstruct path going backwards from e
	path = []
	for(at = 2; at != null; at = prev[at]):
		path.add(at)

	path.reverse()

	// If s and e are connected return the path
	if path[0] == s:
		return path
	return []

BFS Shortest Path on a Grid

Motivation

• Many problems in graph theory can be represented using a grid.

• Grids are a form of implicit graph because we can determine a node's neighbors based on our location within the gride.

• A type of problem that involves finding a path through a grid is solving a maze:

  

• Another example could be routing through obstacles (trees, rivers, rocks, etc) to get to a location:

  

Graph Theory on Grids