【代码解析】图的邻接表、DFS和BFS_根据邻接表写dfs和bfs

邻接表

有如下无向图

邻接表的存储结构如下：

//邻接表链表顶点
typedef struct _ENode
{
	int ivex;
	struct _ENode* next_edge;
}ENode;

//邻接表表顶点
typedef struct _VNode
{
	char data;
	ENode* first_edge;
}VNode;

//邻接表
typedef struct _LGraph
{
	int vexnum;
	int edgnum;
	VNode vexs[MAX];
}LGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

首先定义一个LGraph为邻接表，存储整个图的节点数量和边数，以及所有节点数组；
再定义一个VNode存储每个节点的名称以及该节点的边；如A节点有三条边AD AF AC；
最后定义ENode，存储每一个终点节点在VNode数组中的下标，以及连接下一条边的指针。值得注意的是虽然叫边节点（ENode）实际存储的是边的信息，不是节点。

对邻接表初始化

ENode* node1, * node2;
	LGraph* pG;//pG表示图
	//初始化矩阵
	if ((pG = (LGraph*)malloc(sizeof(LGraph))) == NULL)
		return NULL;
	memset(pG, 0, sizeof(LGraph));//就是把申请的空间内初始化为零

	// 初始化"顶点数"和"边数"
	pG->vexnum = vlen;
	pG->edgnum = elen;
1
2
3
4
5
6
7
8
9
10

初始化邻接表，内存都置为0

记录邻接表的节点和边的数量，都为7

循环读取节点数据，初始化节点数组，边都设为NULL

// 初始化"邻接表"的顶点，边都置空
	for (i = 0; i < pG->vexnum; i++)
	{
		pG->vexs[i].data = vexs[i];
		pG->vexs[i].first_edge = NULL;
	}
1
2
3
4
5
6

两个辅助函数，get_position输入节点名称，返回该节点在节点数组中的下标；
link_last，list为节点中已连接的边；将node连接到list末尾。

//返回ch在矩阵中的位置
static int get_position(LGraph g, char ch)
{
	int i;
	//遍历顶点
	for (i = 0; i < g.vexnum; ++i)
		if (g.vexs[i].data == ch)
			return i;
	return -1;
}

//node链接到list末尾
static void link_last(ENode* list, ENode* node)
{
	ENode* p = list;
	while (p->next_edge)
	{
		p = p->next_edge;
	}
	p->next_edge = node;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

循环读取每一条边，获取起点P1和终点P2的下标；将P1连接到P2节点的边上；P2连接到P1节点的边上。
对于有向图，只把P2连接到P1节点的边上。

//像节点内写入边
	for (i = 0; i < pG->edgnum; i++)
	{
		// 读取边的起始顶点和结束顶点
		c1 = edges[i][0];
		c2 = edges[i][1];

		p1 = get_position(*pG, c1);//p1对应起始顶点下标位置
		p2 = get_position(*pG, c2);//p1对应结束顶点下标位置
		// 初始化node1
		node1 = (ENode*)calloc(1, sizeof(ENode));
		node1->ivex = p2;
		if (pG->vexs[p1].first_edge == NULL)
			pG->vexs[p1].first_edge = node1;
		else
			link_last(pG->vexs[p1].first_edge, node1);
		// 初始化node2
		node2 = (ENode*)calloc(1, sizeof(ENode));
		node2->ivex = p1;
		// 将node2链接到"p2所在链表的末尾"
		if (pG->vexs[p2].first_edge == NULL)
			pG->vexs[p2].first_edge = node2;
		else
			link_last(pG->vexs[p2].first_edge, node2);
	}
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

DFS

深度优先搜索的步骤分为
1.递归下去
顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。

2.回溯上来。
否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。

对于下面的图，DFS的思路如下：

1.递归下去
从A出发，到 C；
发现C还与B连接，还可以走，到B；

2.回溯上来。
到B后没有与其他节点连接，无法继续向下走；便向上回溯到C；
仍然没有与其他节点连接，再回溯到A；

1.递归下去
从A出发，到D；

2.回溯上来。
再回溯到A

1.递归下去
从A出发向下遍历F G E

借助辅助数组visited，初始visited全为0，代表对应下标的节点未被访问。
然后遍历邻接表中的每个节点；如果该节点没有访问就进入DFS函数，进一步向下遍历

void DFSTraverse(LGraph G)
{
	int i;
	int visited[MAX];       // 顶点访问标记

	// 初始化所有顶点都没有被访问
	for (i = 0; i < G.vexnum; i++)
		visited[i] = 0;

	printf("DFS: ");
	//从A开始深度优先遍历
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
			DFS(G, i, visited);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

首先将当前节点p1打印，并标记为已经访问
然后获取当前节点p1连接的下一个顶点p2，如果对应顶点p2没有访问就递归执行DFS
递归出来后就循环对p1连接的其余顶点p3 p4 进行递归

static void DFS(LGraph G, int i, int* visited)
{
	ENode* node;
	visited[i] = 1;//要访问当前结点了，所以打印
	printf("%c ", G.vexs[i].data);
	node = G.vexs[i].first_edge;//拿当前顶点的后面一个顶点
	while (node != NULL)
	{
		if (!visited[node->ivex])//只要对应顶点没有访问过，深入到下一个顶点访问
			DFS(G, node->ivex, visited);
		node = node->next_edge;//某个顶点的下一条边，例如B结点的下一条边
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

BFS

每一次搜索，都会将与该节相连的所有节点全部找完。

从A出发，依次遍历与A连接的C D F
然后从C出发遍历与C相连的B
然后从F出发遍历与F相连的G
然后从G出发遍历与G相连的E

需要借助队列queue和访问数组visited执行，初始化visited中元素为0；
依次遍历邻接表中每个节点；
如果该节点p1没有访问过，就将其入队，并打印标记；
然后将p1出队，遍历p1所有连接的节点p2 p3 …；
如果没有访问过就将顶点入队，并打印标记；
访问完所有与p1相连的顶点后，循环对队中顶点出队，遍历相连顶点操作；
直到队空，就继续遍历邻接表中余下节点。

void BFS(LGraph G)
{
	int head = 0;
	int rear = 0;
	int queue[MAX];     // 辅组队列
	int visited[MAX];   // 顶点访问标记
	int i, j, k;
	ENode* node;

	//每个顶点未被访问
	for (i = 0; i < G.vexnum; i++)
		visited[i] = 0;
	//从零号顶点开始遍历
	printf("BFS: ");
	for (i = 0; i < G.vexnum; i++)//对每个连同分量均调用一次BFS
	{
		if (!visited[i])//如果没访问过，就打印，同时入队,最初是A
		{
			visited[i] = 1;//标记已经访问过
			printf("%c ", G.vexs[i].data);
			queue[rear++] = i;  // 入队列
		}
		while (head != rear) //第一个进来的是A，遍历A的每一条边
		{
			j = queue[head++];  // 出队列
			node = G.vexs[j].first_edge;
			while (node != NULL)
			{
				k = node->ivex;
				if (!visited[k])
				{
					visited[k] = 1;
					printf("%c ", G.vexs[k].data);
					queue[rear++] = k;//类似于树的层次遍历，遍历到的同时入队
				}
				node = node->next_edge;
			}
		}
	}
	printf("\n");
}
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

新开通了本人的公众号，欢迎关注：燕南路GISer ，专注GIS干货分享，不定期更新。
主要兴趣：GIS、时空数据挖掘、python、机器学习深度学习
提问、求资源等都可在公众号后台留言
CSDN的部分内容会重写再搬迁到公众号，欢迎关注！

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

#define MAX 100
#define isLetter(a)  ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
#define LENGTH(a)  (sizeof(a)/sizeof(a[0]))

//邻接表链表顶点
typedef struct _ENode
{
	int ivex;
	struct _ENode* next_edge;
}ENode;

//邻接表表顶点
typedef struct _VNode
{
	char data;
	ENode* first_edge;
}VNode;

//邻接表
typedef struct _LGraph
{
	int vexnum;
	int edgnum;
	VNode vexs[MAX];
}LGraph;

//返回ch在矩阵中的位置
static int get_position(LGraph g, char ch)
{
	int i;
	//遍历顶点
	for (i = 0; i < g.vexnum; ++i)
		if (g.vexs[i].data == ch)
			return i;
	return -1;
}

//node链接到list末尾
static void link_last(ENode* list, ENode* node)
{
	ENode* p = list;
	while (p->next_edge)
	{
		p = p->next_edge;
	}
	p->next_edge = node;
}
/*
 * 创建邻接表对应的图(有向图)
 */
LGraph* create_example_lgraph_directed()
{
	char c1, c2;
	char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
	char edges[][2] = {
		{'A', 'B'},
		{'B', 'C'},
		{'B', 'E'},
		{'B', 'F'},
		{'C', 'E'},
		{'D', 'C'},
		{'E', 'B'},
		{'E', 'D'},
		{'F', 'G'} };
	int vlen = LENGTH(vexs);
	int elen = LENGTH(edges);
	int i, p1, p2;
	ENode* node1;
	LGraph* pG;


	if ((pG = (LGraph*)malloc(sizeof(LGraph))) == NULL)
		return NULL;
	memset(pG, 0, sizeof(LGraph));

	// 初始化"顶点数"和"边数"
	pG->vexnum = vlen;
	pG->edgnum = elen;
	// 初始化"邻接表"的顶点
	for (i = 0; i < pG->vexnum; i++)
	{
		pG->vexs[i].data = vexs[i];
		pG->vexs[i].first_edge = NULL;
	}

	// 初始化"邻接表"的边
	for (i = 0; i < pG->edgnum; i++)
	{
		// 读取边的起始顶点和结束顶点
		c1 = edges[i][0];
		c2 = edges[i][1];

		p1 = get_position(*pG, c1);
		p2 = get_position(*pG, c2);
		// 初始化node1
		node1 = (ENode*)calloc(1, sizeof(ENode));
		node1->ivex = p2;
		// 将node1链接到"p1所在链表的末尾"
		if (pG->vexs[p1].first_edge == NULL)
			pG->vexs[p1].first_edge = node1;
		else
			link_last(pG->vexs[p1].first_edge, node1);
	}

	return pG;
}

//创建邻接表对应的图(用已提供的数据)，无向图
LGraph* create_example_lgraph()
{
	char c1, c2;
	char vexs[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
	char edges[][2] = {
		{'A', 'C'},
		{'A', 'D'},
		{'A', 'F'},
		{'B', 'C'},
		{'C', 'D'},
		{'E', 'G'},
		{'F', 'G'} };
	//记录节点和边的数量
	int vlen = LENGTH(vexs);
	int elen = LENGTH(edges);
	//上面类似一个邻接矩阵存储
	int i, p1, p2;
	ENode* node1, * node2;
	LGraph* pG;//pG表示图
	//初始化矩阵
	if ((pG = (LGraph*)malloc(sizeof(LGraph))) == NULL)
		return NULL;
	memset(pG, 0, sizeof(LGraph));//就是把申请的空间内初始化为零

	// 初始化"顶点数"和"边数"
	pG->vexnum = vlen;
	pG->edgnum = elen;
	// 初始化"邻接表"的顶点，边都置空
	for (i = 0; i < pG->vexnum; i++)
	{
		pG->vexs[i].data = vexs[i];
		pG->vexs[i].first_edge = NULL;
	}
	//像节点内写入边
	for (i = 0; i < pG->edgnum; i++)
	{
		// 读取边的起始顶点和结束顶点
		c1 = edges[i][0];
		c2 = edges[i][1];

		p1 = get_position(*pG, c1);//p1对应起始顶点下标位置
		p2 = get_position(*pG, c2);//p1对应结束顶点下标位置
		// 初始化node1
		node1 = (ENode*)calloc(1, sizeof(ENode));
		node1->ivex = p2;
		if (pG->vexs[p1].first_edge == NULL)
			pG->vexs[p1].first_edge = node1;
		else
			link_last(pG->vexs[p1].first_edge, node1);
		// 初始化node2
		node2 = (ENode*)calloc(1, sizeof(ENode));
		node2->ivex = p1;
		// 将node2链接到"p2所在链表的末尾"
		if (pG->vexs[p2].first_edge == NULL)
			pG->vexs[p2].first_edge = node2;
		else
			link_last(pG->vexs[p2].first_edge, node2);
	}
	return pG;
}

void print_lgraph(LGraph G)
{
	int i;
	ENode* node;

	printf("List Graph:\n");
	for (i = 0; i < G.vexnum; i++)//遍历所有的顶点
	{
		printf("%d(%c): ", i, G.vexs[i].data);
		node = G.vexs[i].first_edge;
		while (node != NULL)//把每个顶点周围的结点都输出一下
		{
			printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data);
			node = node->next_edge;
		}
		printf("\n");
	}
}

/*
 * 深度优先搜索遍历图的递归实现
 */
static void DFS(LGraph G, int i, int* visited)
{
	ENode* node;

	visited[i] = 1;//要访问当前结点了，所以打印
	printf("%c ", G.vexs[i].data);
	node = G.vexs[i].first_edge;//拿当前顶点的后面一个顶点
	while (node != NULL)
	{
		if (!visited[node->ivex])//只要对应顶点没有访问过，深入到下一个顶点访问
			DFS(G, node->ivex, visited);
		node = node->next_edge;//某个顶点的下一条边，例如B结点的下一条边
	}
}

/*
 * 深度优先搜索遍历图
 */
void DFSTraverse(LGraph G)
{
	int i;
	int visited[MAX];       // 顶点访问标记

	// 初始化所有顶点都没有被访问
	for (i = 0; i < G.vexnum; i++)
		visited[i] = 0;

	printf("DFS: ");
	//从A开始深度优先遍历
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])
			DFS(G, i, visited);
	}
	printf("\n");
}

/*
 * 广度优先搜索（类似于树的层次遍历）
 */
void BFS(LGraph G)
{
	int head = 0;
	int rear = 0;
	int queue[MAX];     // 辅组队列
	int visited[MAX];   // 顶点访问标记
	int i, j, k;
	ENode* node;

	//每个顶点未被访问
	for (i = 0; i < G.vexnum; i++)
		visited[i] = 0;
	//从零号顶点开始遍历
	printf("BFS: ");
	for (i = 0; i < G.vexnum; i++)//对每个连同分量均调用一次BFS
	{
		if (!visited[i])//如果没访问过，就打印，同时入队,最初是A
		{
			visited[i] = 1;//标记已经访问过
			printf("%c ", G.vexs[i].data);
			queue[rear++] = i;  // 入队列
		}
		while (head != rear) //第一个进来的是A，遍历A的每一条边
		{
			j = queue[head++];  // 出队列
			node = G.vexs[j].first_edge;
			while (node != NULL)
			{
				k = node->ivex;
				if (!visited[k])
				{
					visited[k] = 1;
					printf("%c ", G.vexs[k].data);
					queue[rear++] = k;//类似于树的层次遍历，遍历到的同时入队
				}
				node = node->next_edge;
			}
		}
	}
	printf("\n");
}
int main()
{
	LGraph* pG;
	pG = create_example_lgraph();
	print_lgraph(*pG);
	DFSTraverse(*pG);//深度优先遍历
    BFS(*pG);//广度优先遍历
	return 0;
}
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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286

新开通了本人的公众号，欢迎关注：燕南路GISer ，专注GIS干货分享，不定期更新。
主要兴趣：GIS、时空数据挖掘、python、机器学习深度学习
CSDN的部分内容会重写再搬迁到公众号，欢迎关注！