学妹问图的搜索算法，我用最通俗易懂的讲解让她学会了

前记

昨天学妹抱怨数据结构中的图的搜索算法。她问：图的搜索算法越看越扎心，有没有什么破解之法。于是我给她从图的邻接矩阵、邻接表的建立算法开始讲起，到邻接矩阵、邻接表的相互转换算法，再到图的BFS和DFS算法，并分析了时间复杂度。最后她哈哈大笑，“我懂了”。

对于图的算法，每个刚接触的人都需要一段时间来理解，特别是第一次接触的时候总是想不通。于是我写这篇文章，用最通俗易懂的语言讲解图的搜索算法，帮助大家理解。

文章的标题只是噱头，作为热爱交流技术的学习者，我们应该脚踏实地，所以我会保证文章的内容都是干货！

正文

邻接矩阵

用一个二维数组存放顶点间关系（边或弧）的数据，称为邻接矩阵

typedef struct { //包含权的邻接矩阵的的定义 int Vertices[Max]; //顶点信息的数组 int Edge[Max][Max]; //边的权信息的数组 int numV; //当前的顶点数 int numE; //当前的边数}Adjmatrix;

• 1
• 2
• 3
• 4
• 5
• 6

创建邻接矩阵

在用户输入要创建图的顶点数和边数后，先对邻接矩阵初始化G->Edge[i][j] = 0，将顶点与顶点的边设为0，用来表示无边。之后用户输入顶点与顶点之间的边的权值。

void CreateMatrix(Adjmatrix *G) //创建邻接矩阵{	int n, e, vi, vj, w, i, j;	FILE *fp;	if ((fp = fopen('D:\\dfs.txt', 'r')) == NULL)	{		printf('Error opening file\n');		exit(1);	}	fscanf(fp, '%d,%d', &n, &e);//读取顶点和边	G->numV = n;	G->numE = e;	for (i = 0; i < n; i++) //图的初始化		for (j = 0; j < n; j++)		{			G->Edge[i][j] = 0;		}	for (i = 0; i < G->numV; i++) //将顶点存入数组中	{		fscanf(fp, '%d', &G->Vertices[i]);//读取顶点和边	}	printf('\n');	for (i = 0; i < G->numE; i++)	{		//若为带权值的图，则w输入对应权值		fscanf(fp, '%d,%d,%d', &vi, &w, &vj);		G->Edge[vi][vj] = w;		G->Edge[vj][vi] = w;	}	fclose(fp);}
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

邻接表

邻接表的结构

图中顶点用一个一维数组存储，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。图中每个顶点vi的所有邻接点构成一个线性表，用单链表存储

typedef struct node{ //顶点数据域 int adjvex;//下标 int weight;//权值 struct node *next;}EdgeNode;typedef struct{ //顶点表结点 int vertex; //顶点数据域 EdgeNode *firstedge;//边链表头指针}HighNode;typedef struct{ HighNode verlist[Max]; int n, e;//n是顶点，e是边}GraphNode;

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

创建邻接表

读取顶点，对于图中每个顶点Vi，将邻接于Vi的所有顶点Vj链成一个单链表，单链表中的节点称为表节点，这个单链表称为顶点Vi的邻接表。对每个顶点的邻接表建立一个头节点，这些头节点以顺序结构存储。为了便于随机访问任意顶点的邻接表，可以将所有点的邻接表的头节点放到一个数组里，这个头节点数组称为顶点表。

void CreateGraph(GraphNode *G)//创建邻接表{	int tail, head, weigh, i;	FILE *fp;	if ((fp = fopen('D:\\dfs.txt', 'r')) == NULL)	{		printf('Error opening file\n');		exit(1);	}	fscanf(fp, '%d,%d', &G->n, &G->e);	for (i = 0; i < G->n; i++)	{		fscanf(fp, '%d', &G->verlist[i].vertex);//读取顶点		G->verlist[i].firstedge = NULL;	}	for (i = 0; i < G->e; i++)//逐条边输入	{		EdgeNode *p = (EdgeNode *)malloc(sizeof(EdgeNode));//建立边结点		fscanf(fp, '%d,%d,%d', &head, &weigh, &tail);		p->adjvex = head;		p->weight = weigh;		p->next = G->verlist[tail].firstedge;		G->verlist[tail].firstedge = p;		//插入tail结点		p = (EdgeNode *)malloc(sizeof(EdgeNode));		p->adjvex = tail;		p->weight = weigh;		p->next = G->verlist[head].firstedge;		G->verlist[head].firstedge = p;	}}
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

邻接矩阵与邻接表转换

一个图的邻接矩阵的表示是唯一的，但其邻接表不唯一。

邻接矩阵转换成邻接表

oid Matrix_toGraph(Adjmatrix *G, GraphNode *p)//邻接矩阵转换成邻接表{ int i, j; EdgeNode *h; for (i = 0; i < G->numV; i++) { p->verlist[i].vertex = G->Vertices[i]; p->verlist[i].firstedge = NULL; } for (i = 0; i < G->numV; i++) { for (j = G->numV - 1; j > i; j--) { h = (EdgeNode *)malloc(sizeof(EdgeNode)); if (G->Edge[i][j])//判断顶点之间是否边 { h->adjvex = i; h->weight = G->Edge[i][j]; h->next = p->verlist[j].firstedge; p->verlist[j].firstedge = h; h = (EdgeNode *)malloc(sizeof(EdgeNode)); h->adjvex = j; h->weight = G->Edge[i][j]; h->next = p->verlist[i].firstedge; p->verlist[i].firstedge = h; } } } p->n = G->numV; p->e = G->numE;}

• 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

邻接表转换成邻接矩阵

void Graph_toMatrix(Adjmatrix *G, GraphNode *p)//邻接表转换成邻接矩阵{	int i, j;	G->numV = p->n;	G->numE = p->e;	EdgeNode *q;	for (i = 0; i < p->n; i++)		for (j = 0; j < p->n; j++)		{			G->Edge[i][j] = 0;		}	for (i = 0; i < p->n; i++)	{		G->Vertices[i] = p->verlist[i].vertex;		q = p->verlist[i].firstedge;		while (q)		{			G->Edge[i][q->adjvex] = q->weight;			G->Edge[q->adjvex][i] = q->weight;			q = q->next;		}	}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

广度优先搜索算法

广度优先搜索算法（BFS）核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。

流程图

矩阵形式的广度优先搜索算法

//Next_vertixNext_vertix(Adjmatrix G, int v, int w)返回顶点v相对于w的下一个邻接顶点的索引void BFSX1(Adjmatrix *G, int k)//矩阵形式的广度优先搜索算法{ int i, j, h = 0, count = 0, Q[Max] = { 0 }, front = 0, last = 0; Q[last++] = k; visited[k] = TRUE; while (front < last) { i = Q[front++];// 出队 for (k = Fir_ver(*G, i); k >= 0; k = Next_vertix(*G, i, k)) { if (!visited[k]) { visited[k] = TRUE; Q[last++] = k;//入队 } } } printf('序号：'); for (i = 0; i < G->numV; i++) { printf('%d ', i); } printf('\n优先编号：'); for (i = 0; i < G->numV; i++) { for (j = 0; j < G->numV; j++) { if (Q[j] == i) { printf('%d ', j); } } }}void Bfst1(Adjmatrix *G){ int i, count = 1; for (i = 0; i < G->numV; i++) { visited[i] = FLASE; } for (i = 0; i < G->numV; i++) { if (!visited[i]) { BFSX1(G, i); } }}

• 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

邻接表形式的广度优先搜索算法

void BFSX2(GraphNode *G, int k)//邻接表形式的广度优先搜索算法{	EdgeNode *p;	que *H[Max];	int i, j, h = 0, count = 0, Q[Max] = { 0 }, bfn[Max], front = 0, last = 0;	bfn[k] = count++;	printf('广度优先序列和编号：\n');	visited[k] = TRUE;//表示结点访问过	Q[last++] = k;//k入队列	while (front < last)	{		i = Q[front++];// 出队		p = G->verlist[i].firstedge;		while (p)		{			if (!visited[p->adjvex])			{				bfn[p->adjvex] = count++;				visited[p->adjvex] = TRUE;				Q[last++] = p->adjvex;//入队				H[h] = (que *)malloc(sizeof(que));				H[h]->head = i;//树边入队				H[h++]->tail = p->adjvex;			}			p = p->next;		}	}	printf('序号：');	for (i = 0; i < G->n; i++)	{		printf('%d ', i);	}	printf('\n优先编号：');	for (i = 0; i < G->n; i++)	{		for (j = 0; j < G->n; j++)		{			if (Q[j] == i)			{				printf('%d ', j);			}		}	}}void Bfst2(GraphNode *G){	int i, count = 1;	for (i = 0; i < G->n; i++)	{		visited[i] = FLASE;	}	for (i = 0; i < G->n; i++)	{		if (!visited[i])		{			BFSX2(G, i);		}	}}
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

深度优先搜索算法

深度优先搜索（DFS）其核心思想：简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

流程图

递归深度度优先搜索算法(邻接矩阵）

void DFSX1(Adjmatrix *G, int k)//从一个顶点出发深度搜索(递归，邻接矩阵）{ int i; printf('优先编号：'); printf('%d ', k); printf('序号：'); visited[k] = TRUE; dfn1[k] = count1++; printf('%d\n', dfn1[k]); for (i = 0; i < G->numV; i++) { if (G->Edge[k][i] && !visited[i]) { DFSX1(G, i); } }}void Dfst1(Adjmatrix *G)//递归形式的深度优先搜索（邻接矩阵）{ int i; for (i = 0; i < G->numV; i++) { visited[i] = FLASE; } for (i = 0; i < G->numV; i++) { if (!visited[i]) { DFSX1(G, i); } }}

• 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

非递归深度优先搜索算法(邻接矩阵）

////Fir_ver(Adjmatrix G, int v)返回顶点v的第一个邻接顶点的索引void Recu_DFSX1(Adjmatrix *G, int k)//从一个顶点出发深度搜索(非递归，邻接矩阵）{	int i;	printf('\n优先编号：');	printf('%d ', k);	printf('序号：');	visited[k] = TRUE;	dfn1[k] = count3++;	printf('%d ', dfn1[k]);	for (i = 0; i < G->numV; i++)	{		if (G->Edge[k][i])//判断 		{			while (!visited[i])			{				printf('\n优先编号：');				printf('%d ', i);				printf('序号：');				visited[i] = TRUE;				dfn1[i] = count3++;				printf('%d\n', dfn1[i]);				i = Fir_ver(*G, i);			}		}	}}void Recu_Dfst1(Adjmatrix *G)//非递归形式的深度优先搜索（邻接矩阵）{	int i;	for (i = 0; i < G->numV; i++)	{		visited[i] = FLASE;	}	for (i = 0; i < G->numV; i++)	{		if (!visited[i])		{			Recu_DFSX1(G, i);		}	}}
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

递归深度度优先搜索算法（邻接表）

void DFSX2(GraphNode *G, int i)//从一个顶点出发深度搜索(递归，邻接表）{ EdgeNode *p; printf('序号：'); printf('%d ', i); printf('优先编号：'); visited[i] = TRUE; dfn2[i] = count2++;//对vi取编号 printf('%d\n', dfn2[i]); p = G->verlist[i].firstedge; while (p)//依次搜索vi的邻接点vj { if (!visited[p->adjvex]) { DFSX2(G, p->adjvex); } p = p->next; }}void Dfst2(GraphNode *G)//递归形式的深度优先搜索（邻接表）{ int i, count = 1; for (i = 0; i < G->n; i++) { visited[i] = FLASE; } for (i = 0; i < G->n; i++) { if (!visited[i]) { DFSX2(G, i); } }}

• 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

非递归深度优先搜索算法（邻接表）

void Recu_DFSX2(GraphNode *G, int i)//从一个顶点出发深度搜索(非递归，邻接表）{	EdgeNode *p, *q;	int m;	printf('序号：');	printf('%d ', i);	printf('\n优先编号：');	visited[i] = TRUE;	dfn2[i] = count4++;//对vi取编号	printf('%d\n', dfn2[i]);	p = G->verlist[i].firstedge;	while (p)	{		q = p;		while (!visited[q->adjvex])//依次搜索vi的邻接点vj		{			printf('序号：');			printf('%d ', q->adjvex);			printf('\n优先编号：');			m = q->adjvex;			visited[q->adjvex] = TRUE;			dfn2[q->adjvex] = count4++;//对vi取编号			printf('%d\n', dfn2[q->adjvex]);			q = (EdgeNode *)malloc(sizeof(EdgeNode));			q = G->verlist[m].firstedge;		}		p = p->next;	}}void Recu_Dfst2(GraphNode *G)//非递归形式的深度优先搜索（邻接表）{	int i;	for (i = 0; i < G->n; i++)	{		visited[i] = FLASE;	}	for (i = 0; i < G->n; i++)	{		if (!visited[i])		{			Recu_DFSX2(G, i);		}	}}
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

总结

1. 邻接表的建立算法时间复杂度是O(N)，邻接矩阵的建立算法时间复杂度是O(N*N)。
2. 两者存储结构不同，存储内容相同，对于空间占用情况，邻接表的空间占用较小。
3. 邻接表形式下的广/深度优先搜索的时间复杂度都是O(N)，邻接表形式下的广/深度优先搜索的时间复杂度都是O(N*N)。

如果有收获？希望老铁们来个三连，点赞、收藏、转发

创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客