数据结构与算法基础-学习-24-遍历之DFS（深度优先搜索）和BFS（广度优先搜索）

news/2024/10/18 3:31:11/

目录

一、遍历定义

二、遍历实质

三、DFS

四、BFS

五、宏定义

六、自定义类型

七、函数实现

1、DFS（邻接矩阵实现）

2、DFS（邻接表实现）

3、BFS（邻接矩阵实现）

4、BFS（邻接表实现）

5、打印邻接矩阵遍历顺序

 6、打印邻接表遍历顺序

八、遍历算法效率分析

1、DFS

2、BFS

九、Linux编译测试

一、遍历定义

从已给的连通图中某一顶点出发，沿着一些边访问遍图中所有顶点，且使每个顶点仅被访问一次，就叫做的图的遍历，它是图的基本运算。

二、遍历实质

找每个顶点的邻接点的过程。

三、DFS

深度优先搜索，英文全称Depth First Search。如下图进行举例说明。

这里以邻接矩阵表示无向图进行举例，生成内容如下：

[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,40    ,32767 ]
[10    ,32767 ,40    ,32767 ,60    ]
[32767 ,50    ,32767 ,60    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12

 我们还需要维护一个Visit数组，用于确认访问过的节点有哪些，0表示没有访问过，1表示访问过。

 例如我们从E出发，Visit数组变为：

从邻接矩阵上看，E->B和E->D，DFS算法是一条道走到黑，先扫到B节点，又发现B节点没有被访问，所以先走E->B。

[32767 ,50    ,32767 ,60    ,32767 ]

Visit数组变为：

从邻接矩阵上看B的情况，可以走B->A和B->E，先发现的A节点，又发现A节点没有被访问，所以先走B->A。

[20    ,32767 ,32767 ,32767 ,50    ]

Visit数组变为：

从邻接矩阵上看A的情况，可以走A->B和A->C，A->D，先发现的B节点，又发现B节点被访问过，所以跳过，再看C节点发现没有被访问，所以先走A->C。

[32767 ,20    ,30    ,10    ,32767 ]

Visit数组变为：

从邻接矩阵上看C的情况，可以走C->A和C->D，先发现的A节点，又发现A节点被访问过，所以跳过，再看D节点发现没有被访问，所以先走C->D。

[30    ,32767 ,32767 ,40    ,32767 ]

Visit数组变为：

 最后发现Visit数组中的所有节点被访问完，退出程序。

四、BFS

广度优先搜索，英文全称Breadth First Search，BFS类似于树的层次遍历，我们可以将图逆时针旋转90度，如下图进行举例说明。

旋转后：

这里以邻接矩阵表示无向图进行举例，生成内容如下：

[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,40    ,32767 ]
[10    ,32767 ,40    ,32767 ,60    ]
[32767 ,50    ,32767 ,60    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12

和DFS一样我们也需要维护一个Visit数组，用于确认访问过的节点有哪些，0表示没有访问过，1表示访问过。

我们还需要维护一个队列，没错思路和层次遍历一样。

 例如我们还是从E出发，Visit数组变为：

队列变为：

[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 4 ]
FrontIndex     : 0
RearIndex      : 1
SqQueueLen     : 1

从邻接矩阵上看E，E->B和E->D，BFS算法是广度优先，会先把E可以访问的节点先都走一遍，判断BD是否被访问，都没有被访问，那就依次访问E->B和E->D。

[32767 ,50    ,32767 ,60    ,32767 ]

Visit数组变为：

队列弹出E，压入BD变为：

[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 1 ,3 ]
FrontIndex     : 1
RearIndex      : 3
SqQueueLen     : 2

队列中弹出B，从邻接矩阵上看B的情况，可以走B->A和B->E，发现A节点没有被访问,压入队列中，E被访问过，不压入，所以走B->A。

[20    ,32767 ,32767 ,32767 ,50    ]

Visit数组变为：

 队列，弹出B，压入A变为：

[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 3 ,0 ]
FrontIndex     : 2
RearIndex      : 4
SqQueueLen     : 2

弹出D,从邻接矩阵上看D的情况，可以走D->A和D->C，D->E，发现A节点被访问过，所以跳过，再看C节点发现没有被访问，所以先走D->C，发现所有节点都被访问，退出程序。

[10    ,32767 ,40    ,32767 ,60    ]

Visit数组变为：

五、宏定义

#define MAX_INT_TYPE_NUM      32767 //网中代表无穷大，也代表顶点个数。
#define MAX_VERTEX_NUM        10000 //顶点数组中存放顶点的最大个数。
#define NET_DIRECTION_FLAG    0     //有向网的标志
#define NET_UNDIRECTION_FLAG  1     //无向网的标志//DFS,BFS
#define VISITED_FLAG          1
#define NOT_VISITED_FLAG      0

六、自定义类型

//DFS,BFS
typedef struct AccessSeqType
{VertexIndexType Array[MAX_VERTEX_NUM];VertexIndexType ArraySize;
}AccessSeqType;

这是一个访问顺序数组，方便查看访问顺序的。

邻接矩阵和邻接表的定义和相关代码可以参考之前的文章《数据结构与算法基础-学习-23-图之邻接矩阵与邻接表》

七、函数实现

1、DFS（邻接矩阵实现）

void DepthFirstSearchUseAMGraph(AMGraph* AMG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;AccessSeq->ArraySize++;VisitedArray[VertexIndex] = VISITED_FLAG;VertexIndexType ColIndex;if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。{return;}//GlobalCnt++;for(ColIndex = 0; ColIndex < AMG->CurVertexNum; ColIndex++){//GlobalCycleCnt++;if(AMG->ArcArray[VertexIndex][ColIndex] != MAX_INT_TYPE_NUM && VisitedArray[ColIndex] == NOT_VISITED_FLAG){DepthFirstSearchUseAMGraph(AMG, ColIndex, VisitedArray, AccessSeq);if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。{break;}}}
}
参数名描述
AMG邻接矩阵。
VertexIndex从哪个顶点索引号开始搜索。
VisitedArray顶点访问数组。
AccessSeq顶点访问顺序数组。

2、DFS（邻接表实现）

void DepthFirstSearchUseAGraph(AGraph* AG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;AccessSeq->ArraySize++;VisitedArray[VertexIndex] = VISITED_FLAG;//GlobalCnt++;if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。{return;}ArcNode* TmpArcNode = AG->Vertices[VertexIndex].FirstArcNodePtr;;while(TmpArcNode != NULL){//GlobalCycleCnt++;if(VisitedArray[TmpArcNode->EndVertexIndex] == NOT_VISITED_FLAG){DepthFirstSearchUseAGraph(AG, TmpArcNode->EndVertexIndex, VisitedArray, AccessSeq);if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。{break;}}TmpArcNode = TmpArcNode->NextNodePtr;}
}
参数名描述
AG邻接表。
VertexIndex从哪个顶点索引号开始搜索。
VisitedArray顶点访问数组。
AccessSeq顶点访问顺序数组。

3、BFS（邻接矩阵实现）

void BreadthFirstSearchUseAMGraph(AMGraph* AMG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{JudgeAllNullPointer(VisitedArray);JudgeAllNullPointer(AccessSeq);SqQueue* SQ              = NULL;VertexIndexType* TmpElem = (VertexIndexType*)MyMalloc(sizeof(VertexIndexType));VertexIndexType  i       = 0;InitSqQueue(&SQ,INT_TYPE_FLAG);//初始化循环顺序队   EnterSqQueue(SQ, &VertexIndex);//将第一个结点压入循环顺序队。VisitedArray[VertexIndex]              = VISITED_FLAG;AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;AccessSeq->ArraySize++;while(GetSqQueueLen(SQ) != 0){PrintfSqQueue(SQ);LeaveSqQueue(SQ, TmpElem);for(i = 0; i < AMG->CurVertexNum; i++){if(AMG->ArcArray[*TmpElem][i] != MAX_INT_TYPE_NUM && VisitedArray[i] == NOT_VISITED_FLAG){EnterSqQueue(SQ, &i);VisitedArray[i]                        = VISITED_FLAG;AccessSeq->Array[AccessSeq->ArraySize] = i;AccessSeq->ArraySize++;if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。{break;}}}if(AccessSeq->ArraySize == AMG->CurVertexNum)//如果所有结点访问完成，退出。{break;}}DestroySqQueue(&SQ);free(TmpElem);TmpElem = NULL;Log("Breadth First Search Use AMGraph OK\n",Debug);
}
参数名描述
AMG邻接矩阵。
VertexIndex从哪个顶点索引号开始搜索。
VisitedArray顶点访问数组。
AccessSeq顶点访问顺序数组。

感觉访问顺序数组满退出这一块，两次break，写成goto是不是好些，大家有想法的可以指点小弟一二。

4、BFS（邻接表实现）

void BreadthFirstSearchUseAGraph(AGraph* AG, VertexIndexType VertexIndex, VertexIndexType* VisitedArray, AccessSeqType* AccessSeq)
{JudgeAllNullPointer(VisitedArray);JudgeAllNullPointer(AccessSeq);SqQueue* SQ              = NULL;VertexIndexType* TmpElem = (VertexIndexType*)MyMalloc(sizeof(VertexIndexType));ArcNode*         TmpNode = NULL;InitSqQueue(&SQ,INT_TYPE_FLAG);//初始化循环顺序队   EnterSqQueue(SQ, &VertexIndex);//将第一个结点压入循环顺序队。VisitedArray[VertexIndex]              = VISITED_FLAG;AccessSeq->Array[AccessSeq->ArraySize] = VertexIndex;AccessSeq->ArraySize++;while(GetSqQueueLen(SQ) != 0){LeaveSqQueue(SQ, TmpElem);TmpNode                                = AG->Vertices[*TmpElem].FirstArcNodePtr;while(TmpNode != NULL){if(VisitedArray[TmpNode->EndVertexIndex] == NOT_VISITED_FLAG){EnterSqQueue(SQ, &(TmpNode->EndVertexIndex));VisitedArray[TmpNode->EndVertexIndex]  = VISITED_FLAG;AccessSeq->Array[AccessSeq->ArraySize] = TmpNode->EndVertexIndex;AccessSeq->ArraySize++;if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。{break;}}TmpNode = TmpNode->NextNodePtr;}if(AccessSeq->ArraySize == AG->VertexNum)//如果所有结点访问完成，退出。{break;}}DestroySqQueue(&SQ);free(TmpElem);TmpElem = NULL;Log("Breadth First Search Use AGraph OK\n",Debug);
}
参数名描述
AG邻接表。
VertexIndex从哪个顶点索引号开始搜索。
VisitedArray顶点访问数组。
AccessSeq顶点访问顺序数组。

5、打印邻接矩阵遍历顺序

Status AMGraphTraverse(void (*Func)(AMGraph*,VertexIndexType,VertexIndexType*, AccessSeqType*),AMGraph* AMG, VertexIndexType VertexIndex)
{JudgeAllNullPointer(AMG);VertexIndexType* VisitedArray = (VertexIndexType*)MyCalloc(AMG->CurVertexNum, sizeof(VertexIndexType));AccessSeqType* AccessSeq      = (AccessSeqType*)MyCalloc(1, sizeof(AccessSeqType));AccessSeq->ArraySize          = 0;Func(AMG, VertexIndex, VisitedArray, AccessSeq);char* string = (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char));CopyStr* PS  = (CopyStr*)malloc(sizeof(CopyStr));InitCopyStr(PS);ExecCopyStr(PS,"Traverse Use AMGraph               : [");VertexIndexType i;for(i = 0; i < AccessSeq->ArraySize; i++){sprintf(string,"%d ,", AccessSeq->Array[i]);ExecCopyStr(PS,string);}PS->String[PS->StrEffectiveLen-1] = ']';ExecCopyStr(PS,"\n");free(AccessSeq);free(VisitedArray);AccessSeq    = NULL;VisitedArray = NULL;PS->String[PS->StrEffectiveLen] = '\0';Log(PS->String, Debug);DestroyCopyStr(PS);free(string);string       = NULL;return SuccessFlag;
}
参数名描述
FuncDFS或BFS函数指针。
AMG邻接矩阵。
VertexIndex从哪个顶点索引号开始搜索。

 6、打印邻接表遍历顺序

Status AGraphTraverse(void (*Func)(AGraph*,VertexIndexType,VertexIndexType*,AccessSeqType*),AGraph* AG, VertexIndexType VertexIndex)
{JudgeAllNullPointer(AG);VertexIndexType* VisitedArray = (VertexIndexType*)MyCalloc(AG->VertexNum, sizeof(VertexIndexType));AccessSeqType* AccessSeq      = (AccessSeqType*)MyCalloc(1, sizeof(AccessSeqType));AccessSeq->ArraySize          = 0;Func(AG, VertexIndex, VisitedArray, AccessSeq);char* string = (char*)MyCalloc(STR_TYPE_SIZE, sizeof(char));CopyStr* PS  = (CopyStr*)malloc(sizeof(CopyStr));InitCopyStr(PS);ExecCopyStr(PS,"Traverse Use AGraph                : [");VertexIndexType i;for(i = 0; i < AccessSeq->ArraySize; i++){sprintf(string,"%d ,", AccessSeq->Array[i]);ExecCopyStr(PS,string);}PS->String[PS->StrEffectiveLen-1] = ']';ExecCopyStr(PS,"\n");free(AccessSeq);free(VisitedArray);AccessSeq    = NULL;VisitedArray = NULL;PS->String[PS->StrEffectiveLen] = '\0';Log(PS->String, Debug);DestroyCopyStr(PS);free(string);string       = NULL;return SuccessFlag;
}
参数名描述
FuncDFS或BFS函数指针。
AG邻接表。
VertexIndex从哪个顶点索引号开始搜索。

八、遍历算法效率分析

1、DFS

用邻接矩阵表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n^2)。

用邻接表表示图，虽然有2e个表结点，但只需要扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。

2、BFS

使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n^2)。

用邻接表表示图，虽然有2e个表结点，但只需要扫描e个结点即可完成遍历，加上访问n个头节点的时间，时间复杂度为O(n+e)。

九、Linux编译测试

[gbase@czg2 Graph]$ make
gcc -Wall -Wextra -O3 ../Log/Log.c ../PublicFunction/PublicFunction.c ../PublicFunction/SqQueue/SqQueue.c Graph.c MinimumSpanningTree.c main.c -o TestGraph -I ../Log/ -I ../PublicFunction/ -I ../Select/ -I ../PublicFunction/SqQueue/
[gbase@czg2 Graph]$ ./TestGraph 
[2023-5]--[ Info  ]--Create Net Data                    : OK
[2023-5]--[ Info  ]--Create Undirection Net Use AMGraph : OK
[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,40    ,32767 ]
[10    ,32767 ,40    ,32767 ,60    ]
[32767 ,50    ,32767 ,60    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12
[2023-5]--[ Info  ]--Create Undirection Net Use AGraph  : OK
[2023-5]--[ Debug ]--Printf AGraph                      :
A : [(2, 30, 0x6f18b0),(1, 20, 0x6f1870),(3, 10, (nil))]
B : [(4, 50, 0x6f18d0),(0, 20, (nil))]
C : [(3, 40, 0x6f1910),(0, 30, (nil))]
D : [(4, 60, 0x6f1950),(2, 40, 0x6f1890),(0, 10, (nil))]
E : [(3, 60, 0x6f1990),(1, 50, (nil))]
VertexNum      : 5
ArcNum         : 12
[2023-5]--[ Debug ]--Traverse Use AMGraph               : [4 ,1 ,0 ,2 ,3 ]
[2023-5]--[ Debug ]--Traverse Use AGraph                : [4 ,3 ,2 ,0 ,1 ]
[2023-5]--[ Debug ]--Init SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 4 ]
FrontIndex     : 0
RearIndex      : 1
SqQueueLen     : 1
Flag           : INT_TYPE_FLAG
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 1 ,3 ]
FrontIndex     : 1
RearIndex      : 3
SqQueueLen     : 2
Flag           : INT_TYPE_FLAG
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--SqQueue Data   :
Data           : [ 3 ,0 ]
FrontIndex     : 2
RearIndex      : 4
SqQueueLen     : 2
Flag           : INT_TYPE_FLAG
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Destroy SqQueue Normal
[2023-5]--[ Debug ]--Breadth First Search Use AMGraph OK
[2023-5]--[ Debug ]--Traverse Use AMGraph               : [4 ,1 ,3 ,0 ,2 ]
[2023-5]--[ Debug ]--Init SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Leave SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Enter SqQueue Normal
[2023-5]--[ Debug ]--Destroy SqQueue Normal
[2023-5]--[ Debug ]--Breadth First Search Use AGraph OK
[2023-5]--[ Debug ]--Traverse Use AGraph                : [4 ,3 ,1 ,2 ,0 ]
[2023-5]--[ Info  ]--Destory Net Data                   : OK
[2023-5]--[ Info  ]--Destory Undirection Net Use AMGraph: OK
[2023-5]--[ Info  ]--Destory Undirection Net Use AGraph : OK


http://www.ppmy.cn/news/107273.html

相关文章

Android build中的envsetup.sh详解

Android build中的envsetup.sh详解

源码基于&#xff1a;Android R 0. 前言 今天在编译项目的时候&#xff0c;想看看 envsetup.sh 中变化了些什么&#xff0c;才想起来编译专栏中好像没有详解该脚本&#xff0c;索性现在空余时间比较多&#xff0c;整理一下方便以后查看。 Android envsetup.sh 为编译前的准备…
阅读更多...
个人博客搭建详细步骤

个人博客搭建详细步骤

1. 安装 jdk 和 tomcat 下面将带大家安装 jdk 和部署 tomcat; 首先在本地下载好 jdk 和 tomcat 安装压缩包在服务器新建一个目录&#xff0c;比如在服务器新建一个目录 soft&#xff0c;上传 jdk, tomcat 到服务器 mkdir soft cd soft rz 选择上传的文件名称 //上传文件新建…
阅读更多...
C高级练习

C高级练习

阅读更多...
2022年长三角高校数学建模竞赛C题隧道的升级改造与设计解题全过程文档及程序

2022年长三角高校数学建模竞赛C题隧道的升级改造与设计解题全过程文档及程序

2022年长三角高校数学建模竞赛 C题 隧道的升级改造与设计 原题再现&#xff1a; 某地现存一旧式双洞隧道&#xff0c;现计划将该隧道在旧貌基础上升级改造。在升级改造前&#xff0c;需进行定标与设计。考虑到该隧道洞壁附着特殊涂料&#xff0c;无人机在洞内通信信号较差&am…
阅读更多...
共同成长 合力致远，就在2023亚马逊云科技合作伙伴峰会

共同成长 合力致远，就在2023亚马逊云科技合作伙伴峰会

在云计算蓬勃发展的今天&#xff0c;在推动业务发展、实现共赢的过程中&#xff0c;价值成就&#xff0c;是亚马逊云科技对合作伙伴自始至终的承诺。为助力合作伙伴成就价值&#xff0c;共建成长路径&#xff0c;2023亚马逊云科技合作伙伴峰会将于6月27日在上海世博中心重磅启幕…
阅读更多...
C语言---分支和循环语句

C语言---分支和循环语句

1、什么是语句 C语言语句可以分为五类&#xff1a; 表达式语句函数调用语句控制语句复合语句空语句 C语言有九种控制语句 可以分成一下三类&#xff1a; 条件判断语句也叫分支语句&#xff1a;if语句&#xff0c;switch语句&#xff1b;循环执行语句&#xff1a;do while语…
阅读更多...
AI创作工具的使用体验报告

AI创作工具的使用体验报告

下面是AI创作工具的使用体验报告&#xff0c;围绕以下三点展开&#xff1a; 一、工具的使用体验如何&#xff1f; CSDN博客AI创作工具是一款非常易用的工具&#xff0c;操作简单&#xff0c;可以很快地开始创建内容。在使用过程中&#xff0c;我发现它的语言模型很智能&#…
阅读更多...
HHDESK及HHDBCS快捷升级功能

HHDESK及HHDBCS快捷升级功能

为提升用户体验&#xff0c;HHDESK及HHDBCS新增了一项功能&#xff0c;一键升级。 1 使用软件时快捷升级 在产品首页点击帮助&#xff0c;选择软件升级 弹出如下对话框&#xff1b;点击确定 随即弹出对话框&#xff1b;点击浏览&#xff0c;选择下载到本机上的新版本产品…
阅读更多...
最新文章

Copyright @ 2022~2023