数据结构――图深度优先遍历的递归实现 - JAVA

一、深度优先遍历 深度优先遍历遍历类似于树的先根遍历，是书的先根遍历的推广。 1.初始状态所有顶点都未被访问，从图中某个顶点v出发，访问此顶点 2.依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有与v有想通路径的顶点都被访问到 3.若图中尚有顶点未被访问，则从此顶点出发，重复1,2。直到所有结点都被访问为止。

 int FirstAdjVex(ALGraph G,VertexType v)
 { // 初始条件: 图G存在,v是G中某个顶点
   // 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
   ArcNode *p;
   int v1;
   v1=LocateVex(G,v); // v1为顶点v在图G中的序号
   p=G.vertices[v1].firstarc;
   if(p)
     return p->adjvex;
   else
     return -1;
 }

 int NextAdjVex(ALGraph G,VertexType v,VertexType w)
 { // 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点
   // 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。
   //           若w是v的最后一个邻接点,则返回-1
   ArcNode *p;
   int v1,w1;
   v1=LocateVex(G,v); // v1为顶点v在图G中的序号
   w1=LocateVex(G,w); // w1为顶点w在图G中的序号
   p=G.vertices[v1].firstarc;
   while(p&&p->adjvex!=w1)      // 指针p不空且所指表结点不是w
     p=p->nextarc;
   if(!p||!p->nextarc)          // 没找到w或w是最后一个邻接点
     return -1;
   else // p->adjvex==w
     return p->nextarc->adjvex;        // 返回v的(相对于w的)下一个邻接顶点的序号
 } 

Boolean visited[MAX_VERTEX_NUM];      // 访问标志数组(全局量)
 void(*VisitFunc)(char* v);           // 函数变量(全局量)
// 从第v个顶点出发递归地深度优先遍历图G。
 void DFS(ALGraph G,int v)
 { 
   int w;
   VertexType v1,w1;
   strcpy(v1,GetVex(G,v));
   visited[v]=TRUE;                 // 设置访问标志为TRUE(已访问)
   VisitFunc(G.vertices[v].data);         // 访问第v个顶点
   for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
     if(!visited[w])
       DFS(G,w);            // 对v的尚未访问的邻接点w递归调用DFS
 }

// 对图G作深度优先遍历。
 void DFSTraverse(ALGraph G,void(*Visit)(char*))
 { 
   int v;
   VisitFunc=Visit;             // 使用全局变量VisitFunc,使DFS不必设函数指针参数
   for(v=0;v