深度优先遍历图--DFS

一. 前言

        图的遍历定义：从已经给出的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

        图的遍历实质：找每个顶点的邻接点的过程。

在找顶点邻接点的过程中，可能会出现重复访问某个邻接点的情况，因此为了避免重复访问，我们需要设置一个辅助数组visited[n]，用来标记每个被访问过的顶点，数组中所有顶点的初始值都为0；如果该顶点被访问了，那么它在对应数组中的值就变为1，告诉我们它已经被访问过了。

图的遍历总共有两种，一种就是深度优先遍历（DFS），另外一种则是广度优先遍历（BFS），这个我们下篇博客上再讲，这里我们主要学习深度优先遍历。

二. 深度优先遍历的原理及操作

        1）首先在一个图中选择一个起始顶点，然后访问这个起始顶点，修改它在辅助数组中的值，表示它已经被访问过了。

        2）接着访问这个起始顶点的任意一个邻接点v1，再修改它在辅助数组中的值，继续访问与v1邻接但还没有被访问过的顶点v2。

        3）然后再从v2出发，进行类似的访问。

        4）一直重复上面的操作，直至到达一个所有邻接点都被访问的顶点u为止。

        5)然后，退回一步，退到前一次刚访问的顶点，看是否还有其它没有被访问的邻接顶点。如果有，就访问这个顶点，然后继续从这个顶点出发，重复与之前类似的访问。如果没有，就继续退回。

重复上面过程，直到连通图中所有顶点都被访问过为止。

这里说的是连通图，如果是非连通图，也很简单，对它的每个连通分量进行上面的操作就可以了。

深度优先遍历有一种一条道路走到黑的意蕴，只要前面有没有被访问过的邻接点，就一直访问下去，直到找不到没有被访问过的邻接点才退回一步，看上一个顶点是否还有没有被访问过的邻接点。

三. 深度优先遍历算法的代码实现

void DFS(AMGraph G,int v){    //图G的类型就为邻接矩阵的类型，在我之前的文章中有
    cout<<v;    //访问这个顶点
    visited[v]=1;   //修改辅助数组里面的值
    for(int i=0;i<G.vexnum;i++){    //查看邻接矩阵中与该顶点相邻接的顶点中是否有没有被访问过
        if((G.arcs[v][i]!=0)&&(!visited[w]))
        DFS(G,i);    //如果有，就对它也进行这样类似的操作，也就是DFS遍历
}

四. 补充非连通图的深度优先遍历

        如下所示，当一个连通分量访问完，在另外一个连通分量中继续选一个顶点作为起始顶点，继续深度优先遍历。