Breadth-First Search (BFS)

The opposite of Depth-First Search would be breadth-first search (BFS).

A breadth-first search algorithm will follow multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction.

In this case, the frontier is managed as a Queue data structure.

• Pros
  • This algorithm is guaranteed to find the optimal solution
• Cons
  • almost guaranteed to take longer than the minimal time to run
  • At worst, this algorithm takes the longest possible time to run

You can use BFS to solve shortest-path problems is it is an unweighted graph (edge weights = constant). If they are weighted, you need something like Dijkstra Algorithm.

Implementation

queue<int> q;
bool visited[N];
int distance[N];
 
visited[x] = true;
distance[x] = 0;
q.push(x);
while (!q.empty()) {
	int v = q.front(); q.pop();
	// process node s
	for (auto u : adj[v]) {
		if (visited[u]) continue;
		visited[u] = true;
		distance[u] = distance[v]+1;
		q.push(u); // Add node u to the queue
	}
}

Clearing up confusion in implementation with DFS

Hmm the stuff I say below is kind of confusing, just my thoughts.

Confusion

Sometimes, when I am rusty, I forget whether I should put the visited[u] inside or outside the for loop. This is pretty important to get right.

Difference with DFS

• In DFS, we visit a node and process it at the same time (within the same function call)
• In BFS, we visit a node, add it to the queue, and then process it at a later time (when we pop the node from the Queue)
  • Mark neighbouring nodes as visited, add them to the queue, and process them as we pop the queue.

If this isn’t clear to you, just try it on the following graph:

Drawing-2023-05-18

• Node 2 gets added twice to the queue for no reason

BFS on trees: There are certain times when I need to keep track of the depth. For these distances, just look at your distance implementation, and do it for the tree. The distance will be equivalent to the “depth of a tree”.

• Oh, for example in this problem: https://leetcode.com/problems/binary-tree-level-order-traversal/

Related

• Bipartite Graph

Old Source Code

# Define the function that removes a node from the frontier and returns it.
def remove(self):
	  # Terminate the search if the frontier is empty, because this means that there is no solution.
	if self.empty():
		raise Exception("empty frontier")
	else:
		# Save the oldest item on the list (which was the first one to be added)
		node = self.frontier[0]
		# Save all the items on the list besides the first one (i.e. removing the first node)
		self.frontier = self.frontier[1:]
		return node

BFS is called complete, since it covers all possible cases:

• It will find the shortest path between the start and the goal if one exists.
• If no path exists that fact will be discovered.

Runtime / Complexity

$V$ are nodes and $E$ are edges.

• Asymptotic running time of BFS is $O(|V|+|E|)$
• The computational complexity is $O(|V|)$ , which is not great in problems of higher dimensions, as the time to run the simulation increases exponentially with dimensionality.

From CS341

This is a nice addition that enables us to keep track of parents and levels.