数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索

图的遍历

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次的次序序列。例如迷宫探索就是把迷宫中的所有路都走一遍。遍历可以解决很多问题，最常见的就是求最短路径。主要有两种搜索算法，深搜和广搜。

深度优先搜索DFS

DFS是对先序遍历的推广。从某个顶点v开始处理v，然后递归的遍历所有与v相邻的顶点。
用图说话，以无向无权图为例。

假如我们现在要从0号顶点开始，遍历上图中全部其他顶点。 首先访问0号顶点，判断与0相邻的顶点2、7、5是否可以访问，刚开始肯定没有。先访问2，再判断与2相邻的顶点是否可以访问，如此反复，经过6、4到7时，发现与7相邻的0和4都已访问过，访问1，1，没有别的点可以访问了，返回到7。与7相邻的都访问完了，返回到4，访问与4相邻的其他顶点。到3，再到5。5没有可访问的，返回到4，4也没有可访问的了，返回到6->2->0。这时返回到了起点，说明遍历完成。

回顾上面的遍历过程，我们发现要完成遍历，必须得有保存每个顶点之间的关系，可以邻接矩阵或者邻接表存储。同时还需要标记每个顶点的访问状态。有必要还需要记录走过的路径。

DFS的伪代码如下：

邻接表实现的代码如下：

/* 邻接表存储的图 - DFS */
 
void Visit( Vertex V )
{
    printf("正在访问顶点%d\n", V);
}
 
/* Visited[]为全局变量，已经初始化为false */
void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
{   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
    PtrToAdjVNode W;
     
    Visit( V ); /* 访问第V个顶点 */
    Visited[V] = true; /* 标记V已访问 */
 
    for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
        if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
            DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
}

BFS

广搜类似于层序遍历，需要用到队列来完成。
假设从图中的某个顶点v出发，在访问v之后依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访向它们的邻接点,并使“先被访问的顶点的邻接点"先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中-个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。换句话说,广度优先搜索遍历图的过程中以0。为起始点，由近至远,依次访问和。有路径相通且路径长度为,2…的顶点。

代码：

/* 邻接矩阵存储的图 - BFS */
 
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。  */
/* 此函数根据图的不同类型要做不同的实现，关键取决于对不存在的边的表示方法。*/
/* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
    return Graph->G[V][W]<INFINITY ? true : false;
}
 
/* Visited[]为全局变量，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
    Queue Q;     
    Vertex V, W;
 
    Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
    /* 访问顶点S：此处可根据具体访问需要改写 */
    Visit( S );
    Visited[S] = true; /* 标记S已访问 */
    AddQ(Q, S); /* S入队列 */
     
    while ( !IsEmpty(Q) ) {
        V = DeleteQ(Q);  /* 弹出V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未访问过 */
            if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                /* 访问顶点W */
                Visit( W );
                Visited[W] = true; /* 标记W已访问 */
                AddQ(Q, W); /* W入队列 */
            }
    } /* while结束*/
}