深度优先遍历的过程
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新的顶点，继续遍历。
template <int max_size>void Digraph<max_size> :: depth_first(void (*visit)(Vertex &)) const
/* Post: The function *visit has been performed at each vertex of the Digraph in depth-first order.
Uses: Method traverse to produce the recursive depth-first order. */
{
bool visited [max_size];
Vertex v;
for (all v in G) visited [v] = false;
for (all v in G) if (!visited [v])
traverse (v, visited, visit);
}
template <int max_size>
void Digraph<max_size>::traverse(Vertex &v, bool visited[ ],void (*visit)(Vertex &)) const
/* Pre: v is a vertex of the Digraph.
Post: The depth-first traversal, using function *visit, has been completed for v and for all vertices that can be reached from v.
Uses: traverse recursively. */
{
Vertex w;
visited [v] = true;
(*visit) (v);
for (all w adjacent to v)
if (!visited [w])
traverse (w, visited, visit);
}
java代码如下： //求DFS的深度优先递归算法 public class DNFSreach {
/** * 这里是文档说明 * 算法如下 *开始 *Start; * * procedure DFS_visit(G,u) * color[u] = Gray;//白色结点u已被发现 * for each edge (u,v)do * if color[u] = White then * DFS_visit(G,v); * repeat color[u]=black;//完成后置u为黑色 * end; * * procedure DFS(G) * for each vertex u 属于V do * color[u] = white * for vertex each u 属于 V do * if color[u]=white * then DFS_visit(G,u) * repeat * * * 构建一个无向图 * 无穷大表示这两个点无边，1表示两者有边 * 白色用1表示，灰色用2表示，黑色用3表示 * 初始状态均为白色 * 搜索中被发现的顶点置为灰色 * 结束时，即其邻接表被完全检索之后，其被置为黑色 * 构建一个color[8]数组，其中color[0]不用 * 初始化为0 * S表示无穷大 * 0 1 2 3 4 5 6 7 8 * ------------------------- * 0 * 1 s 1 1 s s s s s * 2 1 s s 1 1 s s s * 3 1 s s s s 1 1 s * 4 s 1 s s s s s 1 * 5 s 1 s s s s s 1 * 6 s s 1 s s s 1 s * 7 s s 1 s s 1 s s * 8 s s s 1 1 s s s * * 深度优先搜索的结果应该为 * 1-2-4-8-5-3-6-7 * * @param args */ static int color[]; static int d =0; public static void main(String[] args) { int s = Integer.MAX_VALUE; int G[][]={{s,s,s,s,s,s,s,s,s}, {s,s,1,1,s,s,s,s,s}, {s,1,s,s,1,1,s,s,s}, {s,1,s,s,s,s,1,1,s}, {s,s,1,s,s,s,s,s,1}, {s,s,1,s,s,s,s,s,1}, {s,s,s,1,s,s,s,1,s}, {s,s,s,1,s,s,1,s,s}, {s,s,s,s,1,1,s,s,s}}; color = new int [9]; ProcedureDFS(G,9); } public static void ProcedureDFS(int [][]G,int n){ //图是以二维数组的形式保存 //n是二维数组的维数 for(int i=1;i <= n-1;i++){ color[i]=1;//把每一个顶点都置为白色，表示还没搜索 } for(int i=1;i<= n-1;i++){ //对于每一个顶点没被访问的顶点进行访问 if(color[i] == 1){ DFS_visit(G,i);//遍历其访问的顶点 } } }
private static void DFS_visit(int[][] g, int i) { // TODO 自动生成的方法存根 color[i] = 2;//标志为灰色，表示被访问过 d++; if(d != g.length-1) System.out.print(+i+ -> ); if(d == g.length-1){ System.out.println(+i); } for(int t=1;t<= g.length-1;t++){ //邻接点没有被访问到 if(color[t] == 1 && g[i][t] != Integer.MAX_VALUE){ DFS_visit(g,t); } } color[i] = 3;//标志位黑色 } }
