6.3 DEPTH-FIRST AND BREADTH-FIRST TRAVERSAL ALGORITHMS 153
considered again until all of the nodes one edge away have been taken off of
the queue and processed.■ 6.3.3 Traversal Analysis
Our goal for these two traversal algorithms was to create a process that would
visit each node of a connected graph exactly once. We begin our analysis to see
if this has been accomplished. In breadth-first, we moved out from the starting
node. We followed all available edges, unless they led to a node we had already
visited. Does this cause any problem? Any nodes that could be reached from
that node will still be visited but just from a more direct route. Looking back at
Fig. 6.4, we see that we didn’t revisit node 8 after nodes 2 or 3. But anything
that we could reach from node 8 is already being visited because node 8 was
reached in an earlier pass. Looking at it another way, is it possible for there to
be a node in a connected graph that wasn’t visited? Because on each pass we
take one step from a node visited on the last pass, the only way for a node not
to be visited is for it to not be adjacent to a visited node of the graph. But that
would mean that the graph is not connected, which contradicts our statement
that the graph is connected, so all of the nodes must be visited.
A similar thing is true for a depth-first search. In this case, we travel deeply
into the graph until we reach a dead end. Do we then visit all of the remaining
nodes in the process of backtracking? Is it possible that we may have missed a
node in this process? Each time that we reach a dead end, we back up to the
first node that has an unvisited adjacent node. We move to that node and again
begin to travel deeply into the graph. A dead end again causes us to back up to
the first node with an unvisited adjacent node that we find. For a node in the
graph to not be visited at the end of this process means that it must not be
adjacent to any of the nodes visited in the graph. But again, this would mean
that the graph is not connected, which contradicts our statement that it is. All
of the nodes must be visited in this traversal as well.
What about the efficiency of this algorithm? Our assumption is that the
work done as we visit each node is the most complex part of this process. So,
the work done to check to see if an adjacent node has been visited and the work
to traverse the edges is not significant in this case. So the order of the algorithm
is the number of times a node is visited. Because we have said that these algo-
rithms visit each node exactly one time, for a graph with N nodes, the visit pro-
cess will be done N times. These traversals are, therefore, of order O(N).