Graph Traversals: Things to Keep in Mind

1. The terms graph search algorithm and graph traversal algorithm are often used interchangeably, irrespective of the actual purpose of the algorithm.
2. There is generally no special "starting node" from which to begin a traversal, unlike the situation in a tree, where we always begin from the root.
3. In a directed graph (digraph), there may be some starting vertices from which it may not be possible to visit all remaining vertices of the graph by following edges leading away from such a starting vertex. Thus we need to be extra careful if we want to visit all vertices in such a graph. And if an undirected graph is also not connected, there will be some vertices unreachable from some other vertices.
4. Traversing a path consisting of adjacent vertices can lead to a cycle, since a graph can have edges between any two vertices. Thus, if we wish to avoid multiple visits to the same vertex we need to have a way to "mark" a vertex, once it has been visited.
5. If you study trees before graphs, then the depth-first graph traversal algorithm should be recognized as a generalization of the preorder and postorder traversal algorithms used with trees. And similarly, the breadth-first graph traversal algorithm should be recognized as a generalization of the level-order traversal algorithm for trees. On the other hand, if you study graphs first, then when you get to trees you should recognize most of the traversal algorithms you see there as special cases of algorithms already studied.
6. Convention We will assume that any graph of interest will have in each vertex a (unique) key. Then, when performing a traversal, if at any vertex we have a choice of directions in which to proceed, we will always go in the direction of the vertex containing the lowest key and not yet visited.

Depth-First Graph Traversal

The general idea behind a depth-first traversal of a graph is this: Start at any vertex, go off in any direction, and keep going until you can proceed no further. Then, back up till you reach a vertex from which you can again go off in some direction. Go off in that direction till you can't go any further ... and so on. Keep repeating this procedure (being careful to note the places you've already visited so you don't visit them again) until you back up to the starting vertex, at which point you're done. Note that a pre-order tree traversal is one form of a depth-first graph traversal.

Here is the pseudocode:

DoItDepthFirst(graph, startVertex, other_parameters_if_required)
----------------------------------------------------------------
Visit startVertex
Mark startVertex as visited
for every vertex v adjacent to startVertex (in ascending key order)
    DoItDepthFirst(graph, v, other_parameters_if_required)

We follow the convention of going in the direction of the smallest key whenever we have a choice of direction in which to go. This will give us a unique depth-first traversal.

Breadth-First Graph Traversal

The general idea behind a breadth-first traversal of a graph is this: Start at any vertex. Visit all the neighbors of that vertex. Then visit all the neighbors of those neighbors. And so on, until there are no neighbors of neighbors of neighbors ... left to visit. Note that a level-order tree traversal is one form of a breadth-first graph traversal.

Here is the pseudocode

DoItBreadthFirst(graph, startVertex, other_parameters_if_required)
------------------------------------------------------------------
Visit startVertex
Mark startVertex as visited
Put startVertex into a queue
while the queue is not empty
    Remove next vertex v from queue
    for each vertex w adjacent to v (in ascending key order in w)
        if w is not marked as visited
            Visit w
            Mark m as visited
            Put w into the queue

Once again, we follow the convention of going in the direction of the smallest key whenever we have a choice of direction in which to go and, whenever we have a choice of starting points, we also choose the starting point with the smallest key. This will give us a unique breadth-first traversal.