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

简介: 本文主要是学习图的广度优先遍历和图的深度优先遍历

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

一.图的遍历

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

二.广度优先搜索(BFS)

1.基本原理

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

2.举例说明

K4CT.jpg

假设从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函数

void BFS(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函数
void DFS(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>

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef struct {
   
   
    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的第一个邻接点下标
int FirstNeighbor(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;
}

int NextNeighbor(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;
}

void BFS(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执行函数
void BFSTraverse(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函数
void DFS(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执行函数
void DFSTraverse(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]);
    }
}

int main(){
   
   
    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);    
    return 0;
}

六.运行结果

KA24.jpg

此时结果与我们自己遍历一致。

相关文章
解决element-ui上传多张图片时闪动问题
解决element-ui上传多张图片时闪动问题
638 0
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
7616 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
|
9月前
|
开发框架 运维 监控
Spring Boot中的日志框架选择
在Spring Boot开发中,日志管理至关重要。常见的日志框架有Logback、Log4j2、Java Util Logging和Slf4j。选择合适的日志框架需考虑性能、灵活性、社区支持及集成配置。本文以Logback为例,演示了如何记录不同级别的日志消息,并强调合理配置日志框架对提升系统可靠性和开发效率的重要性。
292 5
【verilog】同步复位,异步复位以及异步复位同步释放
该文讨论了数字电路设计中触发器复位机制的三种类型:同步复位、异步复位和异步复位同步释放。同步复位在时钟边沿确保稳定性,但对复位脉冲宽度有要求;异步复位响应快速,但可能受干扰且时序不确定;异步复位同步释放则结合两者的优点。设计时需根据需求权衡选择。文中还给出了Verilog代码示例。
|
12月前
|
机器学习/深度学习 Serverless 索引
分类网络中one-hot的作用
在分类任务中,使用神经网络时,通常需要将类别标签转换为一种合适的输入格式。这时候,one-hot编码(one-hot encoding)是一种常见且有效的方法。one-hot编码将类别标签表示为向量形式,其中只有一个元素为1,其他元素为0。
288 3
|
NoSQL JavaScript 前端开发
SpringBoot+Vue实现校园二手系统。前后端分离技术【完整功能介绍+实现详情+源码】
文章介绍了如何使用SpringBoot和Vue实现一个校园二手系统,采用前后端分离技术。系统具备完整的功能,包括客户端和管理员端的界面设计、个人信息管理、商品浏览和交易、订单处理、公告发布等。技术栈包括Vue框架、ElementUI、SpringBoot、Mybatis-plus和Redis。文章还提供了部分源代码,展示了前后端的请求接口和Redis验证码功能实现,以及系统重构和模块化设计的一些思考。
SpringBoot+Vue实现校园二手系统。前后端分离技术【完整功能介绍+实现详情+源码】
|
机器学习/深度学习 数据可视化 算法
利用 XGBoost 进行时间序列预测
利用 XGBoost 进行时间序列预测
950 0
|
机器学习/深度学习 人工智能 数据可视化
斯坦福博士图解AlphaFold 3:超多细节+可视化还原ML工程师眼中的AF3
【8月更文挑战第8天】AlphaFold 3作为AI领域的重大突破,革新了蛋白质结构预测。斯坦福博士通过图解详析了其内部机制,展示了多尺度建模与图神经网络技术如何提升预测精度。尽管存在数据依赖性和计算成本等挑战,AlphaFold 3仍极大地加速了生物学研究与药物开发进程。论文详情参见:https://www.nature.com/articles/s41586-024-07487-w
520 4
|
NoSQL 安全 Redis
如何查看Redis的用户名和密码
【7月更文挑战第29天】
3737 3
|
设计模式 测试技术 C#
WPF/C#:在WPF中如何实现依赖注入
WPF/C#:在WPF中如何实现依赖注入
373 0