Java Reference
In-Depth Information
/
**
@returnanedge'sweight
*
/
publicintweight(inti,intj){
returnmatrix[i][j];
}
/
**
Set/Getthemarkvalueforavertex
*
/
publicvoidsetMark(intv,intval){Mark[v]=val;}
publicintgetMark(intv){returnMark[v];}
}
Figure11.6
(continued)
11.3
Graph Traversals
Often it is useful 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 traver-
sal 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
may consist of a large collection of states, with connections between various pairs
of states. Solving the problem may require getting from a specified start state to a
specified goal state by moving between states only through the connections. Typi-
cally, 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 may not be possible to reach all vertices from the
start vertex. This occurs when the graph is not connected. Second, the graph may
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 maintaining a
mark bit for each vertex on the graph. At the beginning of the algorithm, the mark
bit for all vertices is cleared. The mark bit for a vertex is set when the vertex is first
visited during the traversal. If a marked 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 the mark bit array. If not all vertices are marked, we
can continue the traversal from another unmarked vertex. Note that this process
