Depth-First Search

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

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.

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 DFS 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,2,5,9,6].

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.

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

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

In class, we will develop a recursive function DFS(graph,source,target) to find the target node, starting with the source node. On your current assignment, one problem to 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 DFS is to use our previous routine for each building.