写在前面：博主是一位普普通通的19届双非软工在读生，平时最大的爱好就是听听歌，逛逛B站。博主很喜欢的一句话花开堪折直须折，莫待无花空折枝：博主的理解是头一次为人，就应该做自己想做的事，做自己不后悔的事，做自己以后不会留有遗憾的事，做自己觉得有意义的事，不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习，在记录知识的同时获得部分浏览量，得到更多人的认可，满足小小的成就感，同时在写博客的途中结交更多志同道合的朋友，让自己在技术的路上并不孤单。

目录:
1.深度优先搜索(DFS)
        深度优先搜索简介
        深度优先搜索代码实现(C语言邻接矩阵完整代码)
2.广度优先搜索(BFS)
        广度优先搜索简介
        广度优先搜索的代码实现(C语言邻接矩阵完整代码)

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

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

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

1.2深度优先搜索代码实现(C语言邻接矩阵完整代码)

#include <stdio.h>#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;//遍历一维数组，找到变量vfor (; i<G->vexnum; i++) {if (G->vexs[i]==v) {break;}}//如果找不到，输出提示语句，返回-1if (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; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j].adj=0;G->arcs[i][j].info=NULL;}}for (int i=0; i<G->arcnum; 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<G.vexnum; i++){if( G.arcs[v][i].adj ){return i;}}return -1; } int NextAdjVex(MGraph G,int v,int w) {//从前一个访问位置w的下一个位置开始，查找之间有边的顶点for(int i = w+1; i<G.vexnum; i++){if(G.arcs[v][i].adj){return i;}}return -1; } void visitVex(MGraph G, int v){printf("%d ",G.vexs[v]); } void DFS(MGraph G,int v){visited[v] = true;//标记为truevisitVex( G, v); //访问第v 个顶点//从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){//如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数if(!visited[w]){DFS(G,w);}} } //深度优先搜索 void DFSTraverse(MGraph G){//int v;//将用做标记的visit数组初始化为falsefor( 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; } //输入 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

2.广度优先搜索(BFS)

2.1广度优先搜索简介

广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。
最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。

还拿图 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

2.2广度优先搜索的代码实现(C语言邻接矩阵完整代码)

#include <stdio.h> #include <stdlib.h> #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;//遍历一维数组，找到变量vfor (; i<G->vexnum; i++) {if (G->vexs[i]==v) {break;}}//如果找不到，输出提示语句，返回-1if (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; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j].adj=0;G->arcs[i][j].info=NULL;}}for (int i=0; i<G->arcnum; 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<G.vexnum; i++){if( G.arcs[v][i].adj ){return i;}}return -1; } int NextAdjVex(MGraph G,int v,int w) {//从前一个访问位置w的下一个位置开始，查找之间有边的顶点for(int i = w+1; i<G.vexnum; i++){if(G.arcs[v][i].adj){return i;}}return -1; } //操作顶点的函数 void visitVex(MGraph G, int v){printf("%d ",G.vexs[v]); } //初始化队列 void InitQueue(Queue ** Q){(*Q)=(Queue*)malloc(sizeof(Queue));(*Q)->next=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数组初始化为falsefor( 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; }

本篇博客转载C语言中文网

总结

以上是生活随笔为你收集整理的一文搞定深度优先搜索(DFS)与广度优先搜索(BFS)【含完整源码】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。