150 GRAPH ALGORITHMS
6.3 Depth-First and Breadth-First Traversal Algorithms
When we work with graphs, there may be times that we wish to do something
to each node in the graph exactly once. For example, there may be a piece of
information that needs to be distributed to all of the computers on a network.
We want this information to get to each computer, and we do not want to give
it to any computer twice. The same thing would be true if we were looking for
information instead of distributing it.
There are two techniques that we will examine that accomplish this tra-
versal. In depth-first, our traversal will go as far as possible down a path before
considering another, and in breadth-first, our traversal will go evenly in many
directions. We now look at these two methods in more detail. For these two
traversal methods, we choose one node in the graph as our starting point. In
our discussion, we use the phrase “visit the node” to represent the action that
needs to be done at each node. For example, if we are searching, visiting the
node would mean that we check it for the information we want. These meth-
ods work with both directed and undirected graphs without any changes. We
will illustrate them with undirected graphs.
Either of these traversal methods can also be used to determine if a graph is
connected. If we create a list of the nodes we visit during our traversal, this list
can be compared to the set of nodes in the graph. If they are the same, the
graph is connected. If they are not, there are some nodes that cannot be
reached from where we started, meaning that the graph is not connected.■ 6.3.1 Depth-First Traversal
In depth-first traversal, we visit the starting node and then proceed to follow
links through the graph until we reach a dead end. In an undirected graph, a
node is a dead end if all of the nodes adjacent to it have already been visited. In
a directed graph, if a node has no outgoing edges, we also have a dead end.
When we reach a dead end, we back up along our path until we find an
unvisited adjacent node and then continue in that new direction. The process
will have completed when we back up to the starting node and all the nodes
adjacent to it have been visited. In illustrating this algorithm and all others in this
chapter, if presented with a choice of two nodes, we will choose the node with
the numerically or alphabetically smaller label. When this algorithm is imple-
mented, that choice will depend on how the edges of the graph are stored.