第六章 图(五)深度优先遍历

第六章 图(五)深度优先遍历

图的遍历概念

1、图的遍历
    　和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。
    　深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。
  注意：
　    以下假定遍历过程中访问顶点的操作是简单地输出顶点。

2、布尔向量visited[0．．n-1]的设置
    　图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。

深度优先遍历(Depth-First Traversal)

1．图的深度优先遍历的递归定义
    　假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
    　图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程
    　设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x 之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

3、深度优先遍历的递归算法
（1）深度优先遍历算法
  typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
  Boolean visited[MaxVertexNum]； //访问标志向量是全局量
  void DFSTraverse(ALGraph *G)
  { //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同
    int i；
    for(i=0;i<G->n;i++)
      visited[i]=FALSE； //标志向量初始化
    for(i=0;i<G->n；i++)
      if(!visited[i]) //vi未访问过
        DFS(G，i)； //以vi为源点开始DFS搜索
   }//DFSTraverse

（2）邻接表表示的深度优先搜索算法
  void DFS(ALGraph *G，int i){
    //以vi为出发点对邻接表表示的图G进行深度优先搜索
    EdgeNode *p；
    printf("visit vertex：％c"，G->adjlist[i].vertex)；//访问顶点vi
    visited[i]=TRUE； //标记vi已访问
    p=G->adjlist[i].firstedge； //取vi边表的头指针
    while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex
      if (!visited[p->adjvex])//若vi尚未被访问
        DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索
      p=p->next； //找vi的下一邻接点
     }
   }//DFS

（3）邻接矩阵表示的深度优先搜索算法
  void DFSM(MGraph *G，int i)
  { //以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵
    int j；
    printf("visit vertex：％c"，G->vexs[i])；//访问顶点vi
    visited[i]=TRUE；
    for(j=0；j<G->n；j++) //依次搜索vi的邻接点
      if(G->edges[i][j]==1&&!visited[j])
        DFSM(G，j)//(vi，vj)∈E，且vj未访问过，故vj为新出发点
   }//DFSM
  注意：
    　遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraph或MGraph类型的参数，而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑，选择指针类型的参数为宜。

4、深度优先遍历序列 
    　对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。
（1）一个图的DFS序列不一定惟一
    　当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之。

（2）源点和存储结构的内容均已确定的图的DFS序列惟一
　　① 邻接矩阵表示的图确定源点后，DFS序列惟一
    　DFSM算法中，当从vi出发搜索时，是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点，若这样的邻接点多于一个，则选中的总是序号较小的那一个。
　　【例】对连通图G7用邻接矩阵表示时，以v0为初始出发点的 DFS遍历过程如下图(a)所示，具体算法的执行过程【参见动画演示】：http://www.shzx.net.cn/cms/oi/images/stories/datastruct/shuju16.swf
DFS序列是v0，v1，v2，v5，v4，v6，v3，v7


　　②只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列
    　邻接表作为给定图的存储结构时，其表示不惟一。因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。
    　因此，只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列。
　　【例】连通图G7用邻接表表示时，以v0为初始出发点的 DFS算法的执行过程和DFS序列。参见动画演示：http://www.shzx.net.cn/cms/oi/images/stories/datastruct/shuju17.swf
　
（3）栈在深度优先遍历算法中的作用
    深度优先遍历过程中，后访问的顶点其邻接点被先访问，故在递归调用过程中使用栈（系统运行时刻栈）来保存已访问的顶点。

5、算法分析
    对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。
    当访问某顶点vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。
    所以，DFSTraverse的时间复杂度为O(n2) （调用DFSM）或0(n+e)（调用DFS）。