For our DFS algorithm we will write a recursive algorithm to do the backtracking.
To keep both the pre-order and post-order labels of the vertices we define a
private inner-class countPair (of class GraphAlgs). The actual recursive search
is also done with a private method called doDFS, which will hide the existence
of the local class countPair.
static private class countPair // private counters for DFS search
{
int cnt1, cnt2;
int inc1() { return ++cnt1; } // increment and return counters
int inc2() { return ++cnt2; }
};
static private void doDFS(Graph G, int v, int[] PreOrder, int[] PostOrder, countPair cnt)
{
PreOrder[v] = cnt.inc1();
Vector nbrs = G.neighbors(v);
for (int i=0; i<nbrs.size(); i++)
{
int u = ((Integer) nbrs.elementAt(i)).intValue();
if ( PreOrder[u] == 0 ) // Have we not seen vertex u before?
{
doDFS(G, u, PreOrder, PostOrder, cnt);
}
}
PostOrder[v] = cnt.inc2();
return;
}
static public int DFS(Graph G, int v, int[] PreOrder, int[] PostOrder)
{
int n = G.order();
for (int i=0; i<n; i++) PreOrder[i] = PostOrder[i] = 0;
// returns number of nodes reached
//
countPair cnt = new countPair();
doDFS(G, v, PreOrder, PostOrder, cnt);
return PostOrder[v];
}
Note that the user has to preallocate the arrays PreOrder and PostOrder before calling the DFS algorithm. Recall that array parameter variables are references to the storage allocated in the calling methods. If we allocated new storage in the method DFS then the calling methods would not be able to access the results. We give a test search program below that calls both the BFS and DFS algorithms on a stream of graphs (either from the keyboard or redirected from a file).
import java.io.*;
public class search {
public static void main(String argv[])
{
try {
// BufferedReader input = new BufferedReader(new FileReader(argv[0]));
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
Graph G = new Graph(input);
int n=G.order(); if ( n == 0 ) break;
System.out.print(G.toStringAdjLists());
int preOrder[] = new int[n];
int postOrder[] = new int[n];
GraphAlgs.BFS(G,0,preOrder);
System.out.print(&#;`¨BFS (levelorder): &#;`¨);
for (int i=0; i<n; i++) System.out.print(preOrder[i] + &#;`¨ &#;`¨);
System.out.print(&#;`¨&#;`
n&#;`¨);
GraphAlgs.DFS(G,0,preOrder,postOrder);
System.out.print(&#;`¨DFS (preorder): &#;`¨);
for (int i=0; i<n; i++) System.out.print(preOrder[i] + &#;`¨ &#;`¨);
System.out.print(&#;`¨&#;`
n&#;`¨);
System.out.print(&#;`¨DFS (postorder): &#;`¨);
for (int i=0; i<n; i++) System.out.print(postOrder[i] + &#;`¨ &#;`¨);
System.out.print(&#;`¨&#;`
n&#;`¨);
}
} catch ( Exception e ) { System.err.println(&#;`¨Exception: &#;`¨+e); }
} // main
} // class search
We run this program on the two graphs of Example 14 below:
$ java search <ex2.lists
9
1 2
0 2 3 4
0 1 4 8
1 5 6
1 2 7 8
3
3
4 8
2 4 7
BFS (levelorder): 1 2 3 4 5 7 8 9 6
DFS (preorder): 1 2 3 7 4 8 9 5 6
DFS (postorder): 9 8 4 7 3 5 6 2 1
7
1 2 3
6
0 4
1 5 6
5
0 2 4 6
BFS (levelorder): 1 2 3 4 6 7 5
DFS (preorder): 1 2 4 7 5 6 3
DFS (postorder): 7 2 5 6 4 3 1
Each graph is echoed to the screen then the pre-order labelings of the BFS and
DFS searches are printed, followed by the post-order labels of the DFS search.
The reader can verify that these labels are consistent with Examples 15 and
17.