数据结构与算法基础-学习-24-图的遍历之DFS（深度优先搜索）和BFS（广度优先搜索）
本文介绍数据结构与算法基础-遍历之DFS（深度优先搜索）和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;
}
| 参数名 | 描述 |
| Func | DFS或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;
}| 参数名 | 描述 |
| Func | DFS或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更多推荐
2
0- 0
已为社区贡献2条内容
所有评论(0)