博客

与树的遍历类似，在此我们希望从图中某一结点出发访遍图中其余结点，且时每一个顶点仅被访问一次。这一过程称为图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。

规则：访问v，逐个从v的邻接点出发，若其未访问则从其开始递归遍历，如此可遍历所有与v 连通的顶点。若尚有顶点未访问，则从其开始重复上述过程。

每个顶点调用DFS，DFS主要操作是查找邻接点，用邻接矩阵存储时查找某顶点的邻接点复杂度O(n)，总复杂度O(n^2).当邻接表存储时查找邻接点总复杂度为O(e)，总复杂度为O(n+e).

输入:创建图。

输出：深度优先遍历顶点序列。

运行结果：

算法实现：

邻接矩阵存储：

bool visited[MVNUM]; //判断结点是否访问
Status (*VisitFunc)(MGraph G,int v); //全局函数指针

遍历完所有与v联通的顶点 查找邻接点。

void DFS(MGraph G,int v){
   //遍历完所有与v联通的顶点 查找邻接点
   VisitFunc(G,v);
   visited[v]=TRUE;
   for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
      if(!visited[w])
          DFS(G,w);
}

图的深度优先遍历.

void DFSTraverse(MGraph G,Status (*visit)(MGraph G,int v)){
   /*图的深度优先遍历
   访问v 逐个从v的邻接点出发，若其未访问则从其开始递归遍历，如此可
   遍历所有与v连通的顶点 若尚有顶点未访问 则从其开始重复上述过程*/
   int v;
   VisitFunc=visit;
   for(v=0;v<G.vexnum;v++) //初始化
       visited[v]=FALSE;
   for(v=0;v<G.vexnum;v++)
       if(!visited[v])
           DFS(G,v);
}

邻接表存储：

void DFSTraverse(ALGraph G,Status (*visit)(ALGraph G,int v)){
    /*图的深度优先遍历
    访问v 逐个从v的邻接点出发 若其未访问则从其开始递归遍历如此
    可遍历所有与v连通的顶点 若尚有顶点未访问，则从其开始重复上
    述过程 */
    int v;
    VisitFunc=visit;
    for(v=0;v<G.vexnum;v++) //初始化
        visited[v]=FALSE;
    for(v=0;v<G.vexnum;v++)
       if(!visited[v])
           DFS(G,v);
}