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

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

1.深度优先搜索

1.深度优先搜索简介

以下图为例：

采用深度优先算法遍历这个图的过程为：

1. 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；
2. 然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；
3. 当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；
4. 通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3 邻接点 V6 ，然后 V7 ；
5. 由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；
6. 最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。

根据上边的过程，可以得到图 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;
    //遍历一维数组，找到变量v
    for (; i<G->vexnum; 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; 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]