Register

19.3. Graph Traversals¶

19.3.1. Graph Traversals¶

Many graph applications need to visit the vertices of a graph in some specific order based on the graph’s topology. This is known as a graph traversal and is similar in concept to a tree traversal. Recall that tree traversals visit every node exactly once, in some specified order such as preorder, inorder, or postorder. Multiple tree traversals exist because various applications require the nodes to be visited in a particular order. For example, to print a BST’s nodes in ascending order requires an inorder traversal as opposed to some other traversal. Standard graph traversal orders also exist. Each is appropriate for solving certain problems. For example, many problems in artificial intelligence programming are modeled using graphs. The problem domain might consist of a large collection of states, with connections between various pairs of states. Solving this sort of problem requires getting from a specified start state to a specified goal state by moving between states only through the connections. Typically, the start and goal states are not directly connected. To solve this problem, the vertices of the graph must be searched in some organized manner.

Graph traversal algorithms typically begin with a start vertex and attempt to visit the remaining vertices from there. Graph traversals must deal with a number of troublesome cases. First, it might not be possible to reach all vertices from the start vertex. This occurs when the graph is not connected. Second, the graph might contain cycles, and we must make sure that cycles do not cause the algorithm to go into an infinite loop.

Graph traversal algorithms can solve both of these problems by flagging vertices as VISITED when appropriate. At the beginning of the algorithm, no vertex is flagged as VISITED. The flag for a vertex is set when the vertex is first visited during the traversal. If a flagged vertex is encountered during traversal, it is not visited a second time. This keeps the program from going into an infinite loop when it encounters a cycle.

Once the traversal algorithm completes, we can check to see if all vertices have been processed by checking whether they have the VISITED flag set. If not all vertices are flagged, we can continue the traversal from another unvisited vertex. Note that this process works regardless of whether the graph is directed or undirected. To ensure visiting all vertices, graphTraverse could be called as follows on a graph $\mathbf{G}$:

static void graphTraverse(Graph G) {
int v;
for (v=0; v<G.nodeCount(); v++) {
G.setValue(v, null); // Initialize
}
for (v=0; v<G.nodeCount(); v++) {
if (G.getValue(v) != VISITED) {
doTraversal(G, v);
}
}
}


Function doTraversal might be implemented by using one of the graph traversals described next.