从零开始学数据结构系列之第四章《图的遍历总代码》

文章目录

概念回顾
- 深度优先遍历（DFS）
- - 概念
  - 图的深度优先遍历
  - 深度优先遍历算法步骤
- 广度优先遍历（BFS）
- - 概念
  - 广度优先遍历算法步骤
程序总代码
往期回顾

概念回顾

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)。
对于图的遍历来，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

深度优先遍历（DFS）

概念

深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS。

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

简单来说就是：

这种遍历方式主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底，不断递归重复此过程，直到所有的顶点都遍历完成。它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

有个简单的口诀可以方便记忆：

一条路走到黑
不到南墙不回头撞墙之后再回头
回头之后再撞墙
直到无墙可撞为止

图的深度优先遍历

深度优先遍历，从初始访问结点出发，初始访问节点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前的第一个邻接结点
我们可以看到，这样的访问策略是优先纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问
显然，深度优先搜索是一个递归的过程

深度优先遍历算法步骤

访问初始结点 v，并标记结点 v 为已访问
查找结点 v 的第一个邻接结点 w
若 w 存在，则继续访问 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个结点继续
若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当作另一个 v ，然后进行步骤 123）
查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3

广度优先遍历（BFS）

概念

广度优先遍历(Breadth First Search)，又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

简单来说就类似于我们之前学的层次遍历

广度优先遍历算法步骤

访问初始结点 v 并标记结点 v 为已访问
结点 v 入队列
当队列非空时，继续执行，否则算法结束
出队列，取得头结点 u
查找结点 u 的第一个邻接结点 w
若结点 u 的邻接结点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤
1. 若结点 w 尚未被访问，则访问结点 w 并标记为已访问
2. 结点 w 入队列
3. 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤6

程序总代码

我们用的是以下这张图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VdtKDkiM-1720206040893)(https://i-blog.csdnimg.cn/direct/b8a615ffedfa487fab7a250e92aecf19.png)]
同时注意，这里是不带权值的图

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 5/*
*	vexs -存放的是顶点，也就是内容，如字符“ABCD”这样子的
*	arcs -存放的是边数，也就是是否相连，相连设为1，不相连设为0
*	vexNum  -存放的是顶点数量
*	arcNum	-存放的是边数，也就是各顶点的连接的总数，注意这边用的是无序，所以要/2，例如AB与BA实际上就是一条，但是数还是会数2条
*/typedef struct Graph 
{char* vexs;int** arcs;int vexNum;int arcNum;
}Graph;typedef struct Queue {int front;int rear;int data[MAXSIZE];
}Queue;Queue* initQueue() 
{Queue* Q = (Queue*)malloc(sizeof(Queue));Q->front = Q->rear = 0;return Q;
}int isFull(Queue* Q) 
{if ((Q->rear + 1) % MAXSIZE == Q->front) {return 1;}else {return 0;}
}int isEmpty(Queue* Q) 
{if (Q->front == Q->rear) {return 1;}else {return 0;}
}int enQueue(Queue* Q, int data) 
{if (isFull(Q)) {return 0;}else {Q->data[Q->rear] = data;Q->rear = (Q->rear + 1) % MAXSIZE;return 1;}
}int deQueue(Queue* Q) 
{if(isEmpty(Q)){return -1;}else {int data = Q->data[Q->front];Q->front = (Q->front + 1) % MAXSIZE;return data;}
}Graph* initGraph(int vexNum) 
{int i=0;Graph *T =(Graph*)malloc(sizeof(Graph));T->vexs =(char*)malloc(sizeof(char) * vexNum);T->arcs =(int**)malloc(sizeof(int*) * vexNum);T->vexNum = vexNum;T->arcNum = 0;for(i=0;i<T->vexNum;i++)T->arcs[i] =(int*)malloc(sizeof(int) * vexNum);return T;
}void createGraph(Graph* G, char* vexs, int* arcs) 
{int i=0,j=0;for(;i<G->vexNum;i++){G->vexs[i] = vexs[i];for(;j<G->vexNum;j++){// 二维数组存放值，差不多就是偏移量计算G->arcs[i][j] = *(arcs + i * G->vexNum +j);if (G -> arcs[i][j])G -> arcNum ++;}}G -> arcNum/=2;
}void DFS(Graph* G, int* visited, int index) 
{int i=0;printf("%c ",G->vexs[index]);visited[index] = 1;for(i=0;i<G->vexNum;i++){if(G->arcs[index][i] && !visited[i])DFS(G,visited,i);}
}void BFS(Graph* G, int* visited, int index) 
{int j = 0;int i = 0;Queue* Q = initQueue();printf("%c ", G -> vexs[index]);visited[index] = 1;enQueue(Q, index);while (!isEmpty(Q)) {i = deQueue(Q);for (j = 0; j < G -> vexNum; j++) {if (G -> arcs[i][j] && !visited[j]) {printf("%c ", G -> vexs[j]);visited[j] = 1;enQueue(Q, j);}}}
}int main() 
{int i = 0;int arcs[5][5] = {0,1,1,1,0,1,0,1,1,1,1,1,0,0,0,1,1,0,0,1,0,1,0,1,0};Graph* G = initGraph(5);int* visited = (int*)malloc(sizeof(int) * G -> vexNum);for (; i < G -> vexNum; i++)visited[i] = 0;createGraph(G, "ABCDE", (int*)arcs);DFS(G, visited, 0);printf("\n");for (i = 0; i < G -> vexNum; i++)visited[i] = 0;BFS(G, visited, 0);printf("\n");return 0;
}

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第三章】《图的定义》
38【第三章】《图的基本概念和术语》
39【第三章】《图的存储结构》
40【第三章】《图的遍历之深度优先遍历》
41【第三章】《广度优先遍历BFS》