学数据结构必看！图的深度优先搜索DFS，广度优先搜索BFS算法c语言实现，超详细注释，小白也能懂。_c语言图广度优先

首先介绍一下两个算法是怎样运行的。

深度优先遍历（DFS）： 深度优先遍历是一种递归的算法，它从图的某个节点开始，先访问该节点，再递归地访问该节点的相邻节点。深度优先遍历的核心思想是“先入后出”，即先访问到一个节点，就把该节点的所有相邻节点都压入一个栈中，然后再按照“后进先出”的原则依次访问栈中的节点，直到遍历完所有节点。

广度优先遍历（BFS）： 广度优先遍历是一种基于队列实现的算法，它从图的某个节点开始，先访问该节点，再将该节点的所有相邻节点加入节点队列中。接着从队列头部取出一个节点，访问该节点，并将该节点的所有相邻节点加入队列中，重复上述过程，直到遍历完所有节点。

对于首次接触图的小白来说，一整套可以运行的，解析详细的代码是十分必要的， 下面提供一个整套的可运行的代码，附带详细的注释，希望你能看懂。

#include <stdio.h>
#include <stdlib.h>
#define MaxV 100
//边节点
typedef struct Arc
{
    int adjvex;         //邻接边所指向的顶点
    struct Arc* next;   //指向下一个邻接边
    int weight;         //边的权重信息（方便后面最短路径和最小生成树的算法执行）
} Arc;
//顶点节点
typedef struct Vex
{
    int data;               //顶点的编号
    struct Arc* firstArc;   //指向第一条邻接的边
} Vex, AdjList[MaxV];       //定义这个结构体叫Vex,一个元素为这个结构体，长度为MaxV的数组叫AdjList.
//图节点
typedef struct Graph
{
    AdjList vlist;          //邻接表
    int vexnum, arcnum;     //图的顶点数和边数
} Graph;
 
int visited[MaxV]; // 用于记录顶点是否被访问过
 
// 打印图的节点
void print(Graph g)
{
    for (int i = 0; i < g.vexnum; i++)
    {
        printf("%d: ", g.vlist[i].data);
        Arc* currentArc = g.vlist[i].firstArc;
        while (currentArc != NULL)
        {
            printf("%d ", currentArc->adjvex);
            currentArc = currentArc->next;
        }
        printf("\n");
    }
}
//访问函数
void visit(int v){
    visited[v] = 1;
    printf("%d ",v);
}
 
void ManualInit(Graph* g)
{
    int vexnum, arcnum;
    scanf("%d %d", &vexnum, &arcnum);
    g->vexnum = vexnum;
    g->arcnum = arcnum;
    // 初始化顶点，在这里为了方便，顶点编号和数组下标一致
    for (int i = 0; i < vexnum; i++)
    {
        g->vlist[i].data = i;
        g->vlist[i].firstArc = NULL; // 初始化第一个邻接边为NULL
    }
    // 初始化边
    for (int i = 0; i < arcnum; i++)
    {
        int v1, v2;
        scanf("%d %d", &v1, &v2);
 
        // 创建新的边节点
        Arc* a1 = (Arc*)malloc(sizeof(Arc));
        a1->adjvex = v2;
        a1->next = g->vlist[v1].firstArc; // 添加到v1的邻接链表头部
        g->vlist[v1].firstArc = a1;
 
        // 如果是无向图，还需要创建一条反向的边
        Arc* a2 = (Arc*)malloc(sizeof(Arc));
        a2->adjvex = v1;
        a2->next = g->vlist[v2].firstArc; // 添加到v2的邻接链表头部
        g->vlist[v2].firstArc = a2;
    }
}
void autoInit(Graph *g){
    int vexnum = 8, arcnum = 10;
    g->arcnum = arcnum;
    g->vexnum = vexnum;
    // 初始化顶点，在这里为了方便，顶点编号和数组下标一致
    for (int i = 0; i < vexnum; i++)
    {
        g->vlist[i].data = i;
        g->vlist[i].firstArc = NULL; // 初始化第一个邻接边为NULL
    }
    //边信息数组
    int arc[][2] = {{1,2},{1,3},{1,4},{2,5},{2,4},{3,6},{3,7},{3,0},{5,7},{7,0}};
    for (int i = 0; i < arcnum; i++)
    {
        int v1 = arc[i][0], v2 = arc[i][1];
        // 创建新的边节点
        Arc* a1 = (Arc*)malloc(sizeof(Arc));
        a1->adjvex = v2;
        a1->next = g->vlist[v1].firstArc; // 添加到v1的邻接链表头部
        g->vlist[v1].firstArc = a1;
 
        // 如果是无向图，还需要创建一条反向的边
        Arc* a2 = (Arc*)malloc(sizeof(Arc));
        a2->adjvex = v1;
        a2->next = g->vlist[v2].firstArc; // 添加到v2的邻接链表头部
        g->vlist[v2].firstArc = a2;
    }
 
}
 
//初始化访问数组
void initVisited(){
    for(int i = 0; i < MaxV; i++){
        visited[i] = 0;
    }
}
 
// 使用递归实现BFS 
void DFS2(Graph g, int start){
    //将起始节点的访问状态设置为1
    visited[g.vlist[start].data] = 1;
    //打印节点
    printf("%d ",start);
    //获得第一个邻接边
    Arc * currentarc = g.vlist[start].firstArc;
    //遍历所有的邻接边
    while(currentarc != NULL){
        //获取邻接的顶点
        int adjvex = currentarc->adjvex;
        //判断其是否在前面的过程中访问过
        if(visited[adjvex] == 0){
            //如果未访问则递归函数，从这个点开始深度向下搜索
            DFS2(g, adjvex);
        }
        //邻接边的更新
        currentarc = currentarc->next;
    }
}
 
void DFSTravers(Graph g){
    //非连通图的深度遍历
    for(int i = 0; i < g.vexnum; i++){
        //从每个顶点都出发深搜一次
        if(visited[i] == 0)
            DFS2(g, i);
    }
}
 
int BFS2(Graph g){
    initVisited();
    //使用数组实现队列
    int queue[MaxV];
    int front = 0, rear = 0;
 
    //添加一个循环，保证非连通的图也可遍历完
    for(int i = 0; i < g.vexnum; i++){
        //判断节点是否访问过，如果未访问，添加到队列待访问。
        if(visited[i] == 0){
            queue[rear++] = i;
        }
        //如果队列不空就一直访问，队列为空结束循环说明连通的节点已经全部访问到了。
        while(front < rear){
            //取队头元素访问。
            int v = queue[front];
            front++;
 
            visit(v);
            //将该元素所指的第一个元素赋值
            Arc* currentArc = g.vlist[v].firstArc;
            //遍历邻接表中所有节点
            while(currentArc != NULL){
                //判断节点是否访问，如果未访问，添加到队列中
                if(visited[currentArc->adjvex] == 0){
                    queue[rear] = currentArc->adjvex;
                    rear++;
                    //一定要在这里添加访问标志，否则会将访问过的节点反复添加。
                    visited[currentArc->adjvex] = 1;
                }
                //继续寻找邻接表中的下一个可达节点
                currentArc = currentArc->next;
            }
        }
    }
}
 
 
int main()
{
    Graph g;
    //手动设置图的数据
    // ManualInit(&g);
    //初始化预设图
    autoInit(&g);
    print(g);
 
    printf("DFS:\n");
    DFSTravers(g);
    //初始化访问数组
    initVisited();
    printf("\n");
 
    printf("BFS:\n");
    BFS2(g);
    return 0;
}

代码中预设的图

如下是程序运行截图