深度优先搜索（dfs、深搜）和广度优先搜索（bfs、广搜）-百家乐凯发k8

前边介绍了有关图的 4 种存储方式，本节介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种：深度优先搜索和广度优先搜索。

深度优先搜索（简称“深搜”或dfs）

图 1 无向图

深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为：

首先任意找一个未被遍历过的顶点，例如从 v1 开始，由于 v1 率先访问过了，所以，需要标记 v1 的状态为访问过；
然后遍历 v1 的邻接点，例如访问 v2 ，并做标记，然后访问 v2 的邻接点，例如 v4 （做标记），然后 v8 ，然后 v5 ；
当继续遍历 v5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 v5 回退到 v8 ，看 v8 是否有未被访问过的邻接点，如果没有，继续回退到 v4 ， v2 ， v1 ；
通过查看 v1 ，找到一个未被访问过的顶点 v3 ，继续遍历，然后访问 v3 邻接点 v6 ，然后 v7 ；
由于 v7 没有未被访问的邻接点，所有回退到 v6 ，继续回退至 v3 ，最后到达 v1 ，发现没有未被访问的；
最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。

根据上边的过程，可以得到图 1 通过深度优先搜索获得的顶点的遍历次序为：

v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7

所谓深度优先搜索，是从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。

深度优先搜索是一个不断回溯的过程。

采用深度优先搜索算法遍历图的实现代码为：

#include 
#define max_vertex_num 20                   //顶点的最大个数
#define vrtype int                          //表示顶点之间的关系的变量类型
#define infotype char                       //存储弧或者边额外信息的指针变量类型
#define vertextype int                      //图中顶点的数据类型
typedef enum{false,true}bool;               //定义bool型常量
bool visited[max_vertex_num];               //设置全局数组，记录标记顶点是否被访问过
typedef struct {
    vrtype adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    infotype * info;                        //弧或边额外含有的信息指针
}arccell,adjmatrix[max_vertex_num][max_vertex_num];
typedef struct {
    vertextype vexs[max_vertex_num];        //存储图中顶点数据
    adjmatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}mgraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int locatevex(mgraph * g,vertextype v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; ivexnum; i  ) {
        if (g->vexs[i]==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i>g->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造无向图
void createdn(mgraph *g){
    scanf("%d,%d",&(g->vexnum),&(g->arcnum));
    for (int i=0; ivexnum; i  ) {
        scanf("%d",&(g->vexs[i]));
    }
    for (int i=0; ivexnum; i  ) {
        for (int j=0; jvexnum; j  ) {
            g->arcs[i][j].adj=0;
            g->arcs[i][j].info=null;
        }
    }
    for (int i=0; iarcnum; i  ) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        int n=locatevex(g, v1);
        int m=locatevex(g, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        g->arcs[n][m].adj=1;
        g->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
    }
}
int firstadjvex(mgraph g,int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i=0; w = nextadjvex(g,v,w)){
        //如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数
        if(!visited[w]){
            dfs(g,w);
        }
    }
}
//深度优先搜索
void dfstraverse(mgraph g){//
    int v;
    //将用做标记的visit数组初始化为false
    for( v = 0; v < g.vexnum;   v){
        visited[v] = false;
    }
    //对于每个标记为false的顶点调用深度优先搜索函数
    for( v = 0; v < g.vexnum; v  ){
        //如果该顶点的标记位为false，则调用深度优先搜索函数
        if(!visited[v]){
            dfs( g, v);
        }
    }
}
int main() {
    mgraph g;//建立一个图的变量
    createdn(&g);//初始化图
    dfstraverse(g);//深度优先搜索图
    return 0;
}

以图 1 为例，运行结果为：

8,9
1
2
3
4
5
6
7
8
1,2
2,4
2,5
4,8
5,8
1,3
3,6
6,7
7,3
1 2 4 8 5 3 6 7

广度优先搜索

广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。

最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。

还拿图 1 中的无向图为例，假设 v1 作为起始点，遍历其所有的邻接点 v2 和 v3 ，以 v2 为起始点，访问邻接点 v4 和 v5 ，以 v3 为起始点，访问邻接点 v6 、 v7 ，以 v4 为起始点访问 v8 ，以 v5 为起始点，由于 v5 所有的起始点已经全部被访问，所有直接略过， v6 和 v7 也是如此。
以 v1 为起始点的遍历过程结束后，判断图中是否还有未被访问的点，由于图 1 中没有了，所以整个图遍历结束。遍历顶点的顺序为：

v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8

广度优先搜索的实现需要借助队列这一特殊数据结构，实现代码为：

#include 
#include 
#define max_vertex_num 20                   //顶点的最大个数
#define vrtype int                          //表示顶点之间的关系的变量类型
#define infotype char                       //存储弧或者边额外信息的指针变量类型
#define vertextype int                      //图中顶点的数据类型
typedef enum{false,true}bool;               //定义bool型常量
bool visited[max_vertex_num];               //设置全局数组，记录标记顶点是否被访问过
typedef struct queue{
    vertextype data;
    struct queue * next;
}queue;
typedef struct {
    vrtype adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    infotype * info;                        //弧或边额外含有的信息指针
}arccell,adjmatrix[max_vertex_num][max_vertex_num];
typedef struct {
    vertextype vexs[max_vertex_num];        //存储图中顶点数据
    adjmatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}mgraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int locatevex(mgraph * g,vertextype v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; ivexnum; i  ) {
        if (g->vexs[i]==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i>g->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造无向图
void createdn(mgraph *g){
    scanf("%d,%d",&(g->vexnum),&(g->arcnum));
    for (int i=0; ivexnum; i  ) {
        scanf("%d",&(g->vexs[i]));
    }
    for (int i=0; ivexnum; i  ) {
        for (int j=0; jvexnum; j  ) {
            g->arcs[i][j].adj=0;
            g->arcs[i][j].info=null;
        }
    }
    for (int i=0; iarcnum; i  ) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        int n=locatevex(g, v1);
        int m=locatevex(g, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        g->arcs[n][m].adj=1;
        g->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
    }
}
int firstadjvex(mgraph g,int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; inext=null;
}
//顶点元素v进队列
void enqueue(queue **q,vertextype v){
    queue * element=(queue*)malloc(sizeof(queue));
    element->data=v;
    element->next = null;
    queue * temp=(*q);
    while (temp->next!=null) {
        temp=temp->next;
    }
    temp->next=element;
}
//队头元素出队列
void dequeue(queue **q,int *u){
    (*u)=(*q)->next->data;
    (*q)->next=(*q)->next->next;
}
//判断队列是否为空
bool queueempty(queue *q){
    if (q->next==null) {
        return true;
    }
    return false;
}
//广度优先搜索
void bfstraverse(mgraph g){//
    int v;
    //将用做标记的visit数组初始化为false
    for( v = 0; v < g.vexnum;   v){
        visited[v] = false;
    }
    //对于每个标记为false的顶点调用深度优先搜索函数
    queue * q;
    initqueue(&q);
    for( v = 0; v < g.vexnum; v  ){
        if(!visited[v]){
            visited[v]=true;
            visitvex(g, v);
            enqueue(&q, g.vexs[v]);
            while (!queueempty(q)) {
                int u;
                dequeue(&q, &u);
                u=locatevex(&g, u);
                for (int w=firstadjvex(g, u); w>=0; w=nextadjvex(g, u, w)) {
                    if (!visited[w]) {
                        visited[w]=true;
                        visitvex(g, w);
                        enqueue(&q, g.vexs[w]);
                    }
                }
            }
        }
    }
}
int main() {
    mgraph g;//建立一个图的变量
    createdn(&g);//初始化图
    bfstraverse(g);//广度优先搜索图
    return 0;
}

例如，使用上述程序代码遍历图 1 中的无向图，运行结果为：

8,9
1
2
3
4
5
6
7
8
1,2
2,4
2,5
4,8
5,8
1,3
3,6
6,7
7,3
1 2 3 4 5 6 7 8

总结

本节介绍了两种遍历图的方式：深度优先搜索算法和广度优先搜索算法。深度优先搜索算法的实现运用的主要是回溯法，类似于树的先序遍历算法。广度优先搜索算法借助队列的先进先出的特点，类似于树的层次遍历。