Breadth-First Search

We previously had a quick introduction to Breadth-First Search (BFS) as well as describing how to implement Depth-First Search (DFS). Today, we will re-introduce BFS and outline how to implement it. We will also see a few variations on the idea.

The goal is identical to DFS. Typically, the overall goal is to find a path to some node in the graph that meets the desired property. What property? In general, we might have some function that, given a node, simply returns true or false. So we could make that function test for anything. But, for simplicity in today's presentation, we'll simply have a node name that we are looking for.

DFS vs. BFS

A key aspect of BFS is that is explores the graph in levels. E.g., it visits all of the nodes that are 2 edges away from the source node before it visits any of the nodes that are 3 edges away from the source. Thus, it will always find a shortest path to the target. This is often a very desirable property.

One scenario in which DFS is more appropriate is when modeling a physical entity moving through a maze or roads. DFS is very natural viewed as a person moving from one node to the next, along edges, backtracking when necessary. BFS, on the other hand, tends to “jump around” much more. A way to view it more physically is with an army of ants that keep splitting up as they get farther from the source.

Examples

The following image shows a graph.

• sampleGraph = {1:[2,3,4], 2:[1,3,5], 3:[1,2], 4:[1,7,9], 5:[2,9], 6:[9], 7:[4], 8:[9], 9:[5,8,6,4]}
      

Each node is named in black. Each node is also labeled in red by the ordering that BFS might search the graph, assuming we start at node 1 and look for node 6. In bold is the found path. We will represent that path as the list of nodes [1,4,9,6]. Note that this happens to be a different path than we observed for DFS.

As another example, using the same graph, DFS would quickly find the path from node 1 to node 1! We represent the path as [1], i.e., start at node 1, and you're done.

The previous examples illustrated a graph that was connected, i.e., for every pair of nodes, there was some way of getting from node X to node Y. That is a typical, but not a necessary assumption. In the following example, again each node is named and labeled with its DFS ordering, assuming we start at node 1 and look for node 11. Once DFS runs out of edges accessible from node 1, it stops and needs to return a value which represents “no path”. There are two reasonable Python candidates for representing the non-existence of a path: the empty list [] and None.

As with DFS, a key issue in BFS is how to avoid going around in circles. We accomplish that with the same idea as in DFS: once we have “visited”, we don't want to visit it again. So, BFS needs to keep track of which nodes it has visited.

Each of these examples used an undirected graph, but BFS works just the same on directed graphs.

In class, we will outline a function BFS(graph,source,target) to find the target node, starting with the source node. On your current assignment, one problem is to implement this function, while another is to then modify that code so that it also returns the path, as outlined above.

A Common Variation

As a variation, consider the following scenario. There are a bunch of buildings, each with halls and rooms. In some rooms, we hope to find treasure, and you want to identify which room(s) have treasure. Unfortunately, you don't have a map.

This scenario is common to many video games, but it is also similar to many real-life situations, where you can only discover what happens by “going there”.

Translating this scenario to a graph problem, the rooms would be nodes, the halls would be edges. The rooms of each building would be connected, but the rooms of one building would be disconnected from those of another building. And, importantly, our graph would be “hidden” from us, i.e., we could only discover a hall or room by going there.

In such a scenario, looking for a path is not necessarily the goal, since the graph is disconnected. Instead, we might just want to find the rooms. Simply looping over a list of all the rooms is not possible, by assumption that we don't have access to the whole graph representation. A simple generalization of BFS is to use our previous routine for each building.

Another Variation

Sometimes BFS is viewed as visiting a group of nodes at a time, rather than a single node. We can view it as visiting all the nodes zero edges away from the source (i.e., just the source node), then all the nodes one edges away from the source, then all the nodes two edges away, etc.

This is useful when we are not looking for simply one target nodes, but all of them that are a given distance away.