图的广度优先遍历和深度优先遍历

前言：在上一篇博客我们学习了图的基本操作，包括图的建立、结点插入与删除等操作，怎么判断我们建立的图是否正确，很简单把它输出出来就是，但是如何输出它，这就是图的遍历问题了。

一.图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
图的遍历比树的遍历要复杂得多，因为图的任意一个顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同- .顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visited[]来标记项点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

二.广度优先搜索（BFS）

1.基本原理

广度优先搜索( Breadth-First-Search, BFS)类似于二叉树的层序遍历算法。基本思想是:首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1, w2…,wn，然后依次访问w1, w2…, wn;的所有未被访问过的邻接顶点;再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。Dijkstra单源最短路径算法和Prim最小生成树算法也应用了类似的思想。换句话说，广度优先搜索遍历图的过程是以v为起始点，由近至远依次访问和v有路径相通且路径长度为1,2,… 的顶点。广度优先搜索是-种分层的查找过程，每向前走一步可能访问-批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一 个辅助队列，以记忆正在访问的顶点的下一层顶点。

2.举例说明

假设从a结点开始访问，a先入队。此时队列非空，取出队头元素a,由于b,c与a邻接且未被访问过，于是依次访问b,c,并将b,c依次入队。队列非空，取出队头元素b,依次访问与b邻接且未被访问的顶点d,e,并将d,e入队(注意: a与b也邻接，但a已置访问标记，故不再重复访问)。此时队列非空，取出队头元素c,访问与c邻接且未被访问的顶点f,g,并将f,g入队。此时，取出队头元素d,但与d邻接且未被访问的顶点为空，故不进行任何操作。继续取出队头元素e,将h入队列…最终取出队头元素h后，队列为空，从而循环自动跳出。遍历结果为abcdefgh。

三.深度优先收索（DFS）

1.基本原理

与广度优先搜索不同，深度优先搜索(Depth-First-Search, DFS)类似于树的先序遍历。如其名称中所暗含的意思-样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某- -起始顶点v,然后由v出发，访问与v邻接且未被访问的任意一个顶点w，再访问与wi邻接且未被访问的任意-一个 顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

2.举例说明

以BFS例子的无向图为例，深度优先搜索的过程:首先访问a,并置a访问标记;然后访问与a邻接且未被访问的顶点b,置b访问标记;然后访问与b邻接且未被访问的顶点d,置d访问标记。此时d已没有未被访问过的邻接点，故返回上一个访问过的顶点b,访问与其邻接且未被访问的顶点e，置e .标…以此类推，直至图中所有的顶点都被访问一次。遍历结果为abdehcfg。

四.核心功能实现

1.BFS函数

voidBFS(Graph *G,char x){int n;for(int i=0;i<G->vertex_num;i++){if(G->vertex[i]==x){
            n=i;break;}}if(n ==-1){printf("Error: 结点不存在\n");}char queue[MAX_VERTEX_NUM], front =-1, rear =-1;          
    queue[++rear]= G->vertex[n];      
    visited[n]= true;while(front !=rear){char current_vertex=queue[++front];printf("%c ",current_vertex);for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){if(!visited[w]){
                queue[++rear]=G->vertex[w];
                visited[w]=true;}}}}

2.DFS函数

//DFS函数voidDFS(Graph *G,char x){int n;for(int i=0;i<G->vertex_num;i++){if(G->vertex[i]==x){
            n=i;break;}}if(n ==-1){printf("Error: 结点不存在\n");}printf("%c ",G->vertex[n]);//访问顶点
    visited2[n]=true;for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))if(!visited2[w]){DFS(G,G->vertex[w]);}}//DFS相比BFS函数，它使用的是栈也就是递归操作

3.效率分析

BFS（广度优先搜索）和DFS（深度优先搜索）是两种不同的图遍历算法，它们的时间和空间复杂度分析也有所不同。

对于BFS算法，其时间复杂度为O(|V|+|E|)，其中|V|表示图中节点的数量，|E|表示边的数量。在BFS中，我们访问每个节点一次，并且遍历了所有与该节点相邻的边，因此时间复杂度为O(|V|+|E|)。对于空间复杂度，BFS需要使用一个队列来存储待访问的节点，因此空间复杂度为O(|V|)，其中最坏情况下所有节点都在队列中。因此，当图稠密时，即|E| ~ |V|^2时，BFS的空间复杂度可能会很高。

对于DFS算法，其时间复杂度与图的连接性质有关，最坏情况下可以达到O(|V|+|E|)。然而，实际应用中，DFS的时间复杂度通常比BFS低。对于空间复杂度，DFS需要使用一个栈来存储待访问的节点，因此在最坏情况下，空间复杂度为O(|V|)，其中最坏情况下整个图都是一条链。因此，当图非常深时，DFS的空间复杂度可能会很高。

总体而言，BFS和DFS的时间复杂度都是O(|V|+|E|)，其中|V|表示图中节点数量，|E|表示边数量。它们的主要区别在于空间复杂度上，BFS需要使用队列存储待访问的节点，空间复杂度为O(|V|)，而DFS需要使用栈存储待访问的节点，空间复杂度为O(|V|)。因此，如果空间复杂度很重要，可以选择DFS；如果需要找到最短路径等问题，可以选择BFS。

五.完整代码

#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_VERTEX_NUM20// 最大顶点数typedefstruct{char vertex[MAX_VERTEX_NUM];// 存放顶点信息int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];// 存放边信息int vertex_num;// 顶点数int edge_num;// 边数} Graph;

bool visited1[MAX_VERTEX_NUM];//BFS访问标记数组
bool visited2[MAX_VERTEX_NUM];//DFS访问标记数组//求图G中顶点x的第一个邻接点下标intFirstNeighbor(Graph *G,char x){int n =-1;//待查询结点在数组里的下标for(int i=0;i<G->vertex_num;i++){if(G->vertex[i]==x){
            n=i;break;}}if(n ==-1){// 如果查询节点不存在printf("Error: 结点不存在\n");}int count=0;int nx;//第一个邻接点在数组里的下标//现在知道了他在第n个，所以我们查询边矩阵第n行中第一个1在哪就知道第一个邻接点是谁for(int j=0;j<G->vertex_num;j++){if(G->edge[n][j]==1) count++;if(count==1){
            nx=j;break;}}return nx;}intNextNeighbor(Graph *G,char x,char y){int n =-1;//待查询结点在数组里的下标for(int i=0;i<G->vertex_num;i++){if(G->vertex[i]==x){
            n=i;break;}}if(n ==-1){// 如果查询节点不存在printf("Error: 结点不存在\n");}int count=0;int ny =-1;//存放返回邻接点数组下标for(int j=0;j<G->vertex_num;j++){if(G->vertex[j]==y){
            ny=j;break;}}int nx =-1;//存放返回邻接点数组下标for(int j=ny+1;j<G->vertex_num;j++){if(G->edge[n][j]==1){
            nx=j;break;}}return nx;}voidBFS(Graph *G,char x){int n;for(int i=0;i<G->vertex_num;i++){if(G->vertex[i]==x){
            n=i;break;}}if(n ==-1){printf("Error: 结点不存在\n");}char queue[MAX_VERTEX_NUM], front =-1, rear =-1;          
    queue[++rear]= G->vertex[n];      
    visited1[n]= true;while(front !=rear){char current_vertex=queue[++front];printf("%c ",current_vertex);for(int w=FirstNeighbor(G,current_vertex);w>=0;w=NextNeighbor(G,current_vertex,G->vertex[w])){if(!visited1[w]){
                queue[++rear]=G->vertex[w];
                visited1[w]=true;}}}}//你以为这就是执行函数吗？如果你这样做存在多个连通分量绝对出错//BFS执行函数voidBFSTraverse(Graph *G){for(int i=0;i<G->vertex_num;i++){
        visited1[i]=false;//标记数组初始化}for(int i=0;i<G->vertex_num;++i){if(!visited1[i])BFS(G,G->vertex[i]);}}//DFS函数voidDFS(Graph *G,char x){int n;for(int i=0;i<G->vertex_num;i++){if(G->vertex[i]==x){
            n=i;break;}}if(n ==-1){printf("Error: 结点不存在\n");}printf("%c ",G->vertex[n]);//访问顶点
    visited2[n]=true;for(int w=FirstNeighbor(G,G->vertex[n]);w>=0;w=NextNeighbor(G,G->vertex[n],G->vertex[w]))if(!visited2[w]){DFS(G,G->vertex[w]);}}//DFS相比BFS函数，它使用的是栈也就是递归操作//DFS执行函数voidDFSTraverse(Graph *G){for(int i=0;i<G->vertex_num;i++){
        visited2[i]=false;//标记数组初始化}for(int i=0;i<G->vertex_num;++i){if(!visited2[i])DFS(G,G->vertex[i]);}}intmain(){
    Graph G;
    G.vertex_num=5;
    G.edge_num=6;//人为构造图的顶点for(int i=0;i<G.vertex_num;i++){
        G.vertex[i]='A'+i;}for(int i=0; i<G.vertex_num; i++){for(int j=0; j<G.vertex_num; j++){
            G.edge[i][j]=0;}}//人为构造图的边
    G.edge[0][1]=1;
    G.edge[0][3]=1;
    G.edge[1][2]=1;
    G.edge[2][3]=1;
    G.edge[1][4]=1;
    G.edge[2][4]=1;printf("BFS的遍历结果为：");BFSTraverse(&G);printf("\n");printf("DFS的遍历结果为：");DFSTraverse(&G);return0;}

六.运行结果