一、介绍:

BFS:这是一种基于队列这种数据结构的搜索方式,它的特点是由每一个状态可以扩展出许多状态,然后再以此扩展,直到找到目标状态或者队列中头尾指针相遇,即队列中所有状态都已处理完毕。

DFS:基于递归的搜索方式,它的特点是由一个状态拓展一个状态,然后不停拓展,直到找到目标或者无法继续拓展结束一个状态的递归。

优缺点:

BFS:对于解决最短或最少问题特别有效,而且寻找深度小,但缺点是内存耗费量大(需要开大量的数组单元用来存储状态)。

DFS:对于解决遍历和求所有问题有效,对于问题搜索深度小的时候处理速度迅速,然而在深度很大的情况下效率不高

总结:不管是BFS还是DFS,它们虽然好用,但由于时间和空间的局限性,以至于它们只能解决数据量小的问题。

二、过程

1.广度优先搜索(BFS)

广度优先搜索在进一步遍历图中顶点之前,先访问当前顶点的所有邻接结点。

a .首先选择一个顶点作为起始结点,并将其染成灰色,其余结点为白色。
  b. 将起始结点放入队列中。
  c. 从队列首部选出一个顶点,并找出所有与之邻接的结点,将找到的邻接结点放入队列尾部,将已访问过结点涂成黑色,没访问过的结点是白色。如果顶点的颜色是灰色,表示已经发现并且放入了队列,如果顶点的颜色是白色,表示还没有发现。
  d. 按照同样的方法处理队列中的下一个结点。

基本就是出队的顶点变成黑色,在队列里的是灰色,还没入队的是白色。
用一副图来表达这个流程如下:

img

1.初始状态,从顶点1开始,队列={1}

img

2.访问1的邻接顶点,1出队变黑,2,3入队,队列={2,3,}

img

3.访问2的邻接结点,2出队,4入队,队列={3,4}

img

4.访问3的邻接结点,3出队,队列={4}

img

5.访问4的邻接结点,4出队,队列={ 空}

从顶点1开始进行广度优先搜索:

初始状态,从顶点1开始,队列={1}

访问1的邻接顶点,1出队变黑,2,3入队,队列={2,3,}

访问2的邻接结点,2出队,4入队,队列={3,4}

访问3的邻接结点,3出队,队列={4}

访问4的邻接结点,4出队,队列={ 空}

结点5对于1来说不可达。

2.深度优先搜索(DFS)

深度优先搜索在搜索过程中访问某个顶点后,需要递归地访问此顶点的所有未访问过的相邻顶点。

初始条件下所有节点为白色,选择一个作为起始顶点,按照如下步骤遍历:

a. 选择起始顶点涂成灰色,表示还未访问

b. 从该顶点的邻接顶点中选择一个,继续这个过程(即再寻找邻接结点的邻接结点),一直深入下去,直到一个顶点没有邻接结点了,涂黑它,表示访问过了

c. 回溯到这个涂黑顶点的上一层顶点,再找这个上一层顶点的其余邻接结点,继续如上操作,如果所有邻接结点往下都访问过了,就把自己涂黑,再回溯到更上一层。

d. 上一层继续做如上操作,知道所有顶点都访问过。

用图可以更清楚的表达这个过程:(注意:图画错了,请将3->4这条路径理解成4->3)

img

1.初始状态,从顶点1开始

img

2.依次访问过顶点1,2,3后,终止于顶点3(注意,是4->3)

img

3.从顶点3回溯到顶点2,继续访问顶点5,并且终止于顶点5

img

4.从顶点5回溯到顶点2,并且终止于顶点2

img

5.从顶点2回溯到顶点1,并终止于顶点1

img

6.从顶点4开始访问,并终止于顶点4

从顶点1开始做深度搜索:

初始状态,从顶点1开始

依次访问过顶点1,2,3后,终止于顶点3(再次提醒,4->3)

从顶点3回溯到顶点2,继续访问顶点5,并且终止于顶点5

从顶点5回溯到顶点2,并且终止于顶点2

从顶点2回溯到顶点1,并终止于顶点1

从顶点4开始访问,并终止于顶点4

三、代码应用

为了更方便调试和更细微的观察两种算法的区别,我特地写了一个可以对无向图有向图分别操作的一个小工具。

image-20211223171637485

image-20211223171506570

image-20211223171753096

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
#define TRUE 1
#define FALSE 0

typedef char VertexType;
typedef enum { UDG, DG } GraphType;
typedef struct
{
VertexType Vertex[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
GraphType Mtype;
int arcnum, vernum; //图当前的定点数和弧(或边)数
}MGraph;

void CreateMGraph(MGraph *MG)
{
int i, j, k, m, row = 0, line = 0;
VertexType c, tail, top;
printf("请输入图的类型1(有向图),0为无向图:");
scanf("%d", &MG->Mtype);
printf("\n请输入顶点数:");
scanf("%d", &MG->vernum);
printf("\n请输入边数:");
scanf("%d", &MG->arcnum);
getchar();
//初始化邻接矩阵
for (i = 0; i < MG->vernum; i++)
for (j = 0; j < MG->vernum; j++)
MG->arcs[i][j] = 0;
//初始化顶点数组
printf("\n请输入顶点元素:");
scanf("%c", &c);
for (k = 0; k < MG->vernum; k++)
{
MG->Vertex[k] = c;
scanf("%c", &c);
}
//getchar();
//输入图的边
for (m = 0; m < MG->arcnum; m++)
{
printf("\n请输入第%dth条边:", m + 1);
scanf("%c", &tail);
scanf("%c", &top);
//根据边写入对应邻接矩阵
for (i = 0; i < MG->vernum; i++)
{
if (MG->Vertex[i] == tail)
{
row = i;
break;
}
}
for (j = 0; j < MG->vernum; j++)
{
if (MG->Vertex[j] == top)
{
line = j;
break;
}
}
if (row != line)
MG->arcs[row][line] = MG->arcs[line][row] = 1; //无向图邻接矩阵沿对角线对称
else
printf("\n输入第%dth条边出错,请重试", m);
getchar();
}

}

void printMG(MGraph MG)
{
int i, j;
for (i = 0; i < MG.vernum; i++)
{
printf("\n");
for (j = 0; j < MG.vernum; j++)
printf("%d ", MG.arcs[i][j]);
}
printf("\n\n");
}

void GraphBFS(MGraph MG)
{
//初始化visit数组,0表示顶点还没有搜索,1表示顶点已搜索
int i, j, visit[MAX_VERTEX_NUM] = { 0 };
//初始化队列,这里用队列的顺序存储结构:一维数组,外加一个记录队列头元素位置的变量front、一个记录队列尾元素位置的变量rear
VertexType Queue[MAX_VERTEX_NUM];
int front = 0, rear = 0; //即分别指向数组下标
//选图第一个顶点入队列
Queue[rear++] = MG.Vertex[0];
visit[0] = 1;
while (rear != front)
{
//顶点出队列
printf("队列弹出的BFS顶点依次为:%c\n", Queue[front]);
for (i = 0; i < MG.vernum; i++)
{
if (MG.Vertex[i] == Queue[front])
{
for (j = 0; j < MG.vernum; j++)
{
//顶点入队列
if (MG.arcs[i][j] == 1 && visit[j] == 0)
{
Queue[rear++] = MG.Vertex[j];
visit[j] = 1;
}
}
break;
}
}
front++;
}
//只考虑简单情况,即图是连通图,一次广度优先搜索就能遍历所有顶点
for (i = 0; i < MG.vernum; i++)
if (0 == visit[i]) printf("BFS错误,检查图是否有误,是否是连通图,请重试!\n");
}

void GraphDFS(MGraph MG)
{
//初始化visit数组,0表示顶点还没有搜索,1表示顶点已搜索
int i, j, k, bool1 = TRUE, visit[MAX_VERTEX_NUM] = { 0 };
//初始化堆栈,这里用堆栈的顺序存储结构:一维数组,外加一个记录栈顶元素位置的变量top、一个记录栈底元素位置的变量base
VertexType Stack[MAX_VERTEX_NUM];
int top = 0, base = 0; //即分别指向数组下标
//选图第一个顶点入栈
Stack[top++] = MG.Vertex[0];
visit[0] = 1;
printf("\n入栈DFS顶点依次为:%c\n", Stack[top - 1]);
k = 0;
while (top != base)
{
while (bool1)
{
bool1 = FALSE;
for (j = 0; j < MG.vernum; j++)
{
//顶点入栈
if (1 == MG.arcs[k][j] && 0 == visit[j])
{
bool1 = TRUE;
Stack[top++] = MG.Vertex[j];
visit[j] = 1;
printf("入栈DFS顶点依次为:%c\n", Stack[top - 1]);
k = j;
break;
}
}
}
//顶点出栈
top--;
if (top != base)
{
for (i = 0; i < MG.vernum; i++)
if (Stack[top - 1] == MG.Vertex[i])
{
bool1 = TRUE;
k = i;
break;
}
}
}
//只考虑简单情况,即图是连通图,一次深度优先搜索就能遍历所有顶点
for (i = 0; i < MG.vernum; i++)
if (0 == visit[i]) printf("DFS错误,检查图是否有误,是否是连通图,请重试!\n");
}

////用递归的方式深度优先搜索图,代码就显得很简单
//TraverseGraph(int k, MGraph MG, int visit[])
//{
// int j;
// for (j = 0; j < MG.vernum; j++)
// if (MG.arcs[k][j] == 1 && visit[j] == 0)
// {
// visit[j] = 1;
// k = j;
// printf("DFS顶点依次为:%c\n", MG.Vertex[k]);
// TraverseGraph(k, MG, visit);
// }
//}
//
//void GraphDFS(MGraph MG)
//{
// //初始化visit数组,0表示顶点还没有搜索,1表示顶点已搜索
// int i, k, visit[MAX_VERTEX_NUM] = { 0 };
// //给定第一个元素
// visit[0] = 1;
// k = 0;
// printf("\nDFS顶点依次为:%c\n", MG.Vertex[k]);
// TraverseGraph(k, MG, visit);
// //只考虑简单情况,即图是连通图,一次深度优先搜索就能遍历所有顶点
// for (i = 0; i < MG.vernum; i++)
// if (0 == visit[i]) printf("DFS错误,检查图是否有误,是否是连通图,请重试!\n");
//}

int main()
{
MGraph MG;
CreateMGraph(&MG);
printMG(MG);
GraphBFS(MG);
GraphDFS(MG);
getchar();
}

四、调试分析

这个程序想要调试还是很简单的,首先我写的时候只用了printf并没有用puts,这样就相当于我设置了大量的已知断点。

首先断点到要分析的地方:
image-20211223173335845

此刻栈里面存储着的就是当前图的节点信息,然后观察寄存器 RSI 就可以看到程序每一步的细节。

image-20211223173541404

五-壁纸

5e09a5c1d17b5