前言

图比较复杂，涉及的算法相对较多。

图的定义

图，就是例如下图的东西，图可以分为

  • 有向图：即带有明确的方向指向的图，可以使用 $<a,c>$ 表示从 A 到 C 顶点的路径
  • 无向图：不带有明确的方向指向的图，可以使用 $(a,c)$ 表示从 A 到 C 顶点的路径
image-20220829004344707

图注：有向图

image-20220829024720161

图注：无向图

对于图来说，要求边的两端必须存在“顶点”，否则它不是图。同样的，对于图来说，也不存在空图的概念。

从图的结构来说，又可以分为：简单图和多重图。

  • 简单图
    1. 不存在重复边
    2. 不存在顶点到自身的边
  • 多重图
    1. 允许重复边
    2. 允许存在顶点到自身的边

图的基本概念

  • 图的阶：图里面的顶点（或者叫结点）个数

  • 顶点的度

    • 无向图：顶点的边数
    • 有向图：入度 + 出度
      • 出度：从顶点指向外面顶点的边
      • 入度：指向顶点的边

  • 路径：两个顶点之间的顶点序列，例如下图：A 到 B 的路径为：A,C,B

    image-20220829025426751

  • 回路：第一个顶点和最后一个顶点相同的路径

  • 简单路径：在路径序列中，顶点不重复出现的路径

  • 简单回路：除了第一个顶点和最后一个顶点外，其余顶点不出现重复的回路

  • 路径长度：路径上边的数目

  • 点到点的距离：从顶到到另一个顶点的最短路径作为距离，如果不存在最短路径，则认为两点不存在路径，记作 $\infty$

  • 连通：在无向图中，顶点和顶点间存在路径

  • 强连通：在有向图中，顶点和顶点间存在相互路径

  • 完全图

    • 无向完全图：无向图中任意两个顶点之间都存在边
    • 有向完全图：有向图中任意两个顶点之间存在反复相反的两条弧

图的存储结构

图的存储结构可以分为：

  • 邻接矩阵
  • 邻接表
  • 十字链表
  • 邻接多重表

如上的存储结构（方法），是对无向图和有向图的不同解决方案。

邻接矩阵

邻接矩阵的思路很简单，将顶点序列建立二维数组，用 0 或者 1 来表示顶点间的连通性，图示如下：

image-20220829030718451

图片来源：王道《数据结构》

如上的存储方式可以采用二维数组的方式来存储，代码示例：

1
2
3
4
5
6
7
8
#define Maxsize 100
#define ElemType int
//邻接矩阵
typedef struct {
	char Vertex[Maxsize];	//存放顶点的数组
	ElemType Edge[Maxsize][Maxsize];	//存放顶点关系的数组
	int vexnum, arcnum;	//图的总共顶点数和弧的数目
}Chart;

如上可知：对于邻接矩阵来说，最大的问题是如果存储的边的密度很低的话，会造成大量的空间浪费。

邻接矩阵的性质

如果将邻接矩阵与自身相乘（矩阵相乘），则对应的结果表示了顶点和顶点间是否存在路径为 1 的路径，如下图所示：

image-20220829031641842

图片来源：王道《数据结构》

同理，如果你将其与自身相乘 n 次，则对应的结果意味着顶点和顶点间是否存在长度为 n 的路径。

邻接表

邻接表采用顺序存储和链式存储相互结合的方法，如下图所示，你会发现它和树部分的“孩子表示法”很类似。

image-20220829031940891

图片来源：王道《数据结构》

图示逻辑上理解起来类似于树的“堂兄弟表示法”，代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define Maxsize 100
#define ElemType int

//边，弧
typedef struct ArcNode{
	int adjvex;		//弧指向的结点
	struct ArcNode* next;	//指向下条弧的指针
}ArcNode;

//顶点
typedef struct {
	ElemType data;	//顶点信息
	ArcNode* first;	//第一条边
}VNode,AdjList[Maxsize];

//图
typedef struct {
	AdjList vertices;	//数组存储顶点
	int vexnum, arcnum;	//图的总共顶点数和弧的数目
};

邻接表法的缺点是：寻找顶点的入度或者入边很不方便。

十字链表

注：十字链表是用来存储有向图而设计的。具体示例如下图所示：

image-20220829033432151

图片来源：王道《数据结构》

邻接多重表

对于邻接矩阵存储无向图来说，会存在大量的数据冗余和空间浪费，而邻接多重表就是为了解决这两个问题而产生的解决方案，示例如下图：

image-20220829033710277

注：邻接多重表是用来存储无向图而设计的。

图的基本操作

操作 说明
Adjacent(G,X,Y) 判断图 G 是否存在边 <x,y> 或者 (x,y)
NeighBors(G,X) 列出图 G 中与结点 X 邻接的边
InsertVertex(G,X) 在图 G 中插入顶点 X
DeleteVertex(G,X) 在图 G 中删除顶点 X
AddEdge(G,X,Y) 若无向边 (x,y) 或者有向边 <x,y> 不存在，则向图 G 中添加该边
FirstNeighbor(G,X) 求图 G 中顶点 X 的第一个邻接点，若存在则返回顶点号，不存在返回 -1
NextNeighbor(G,X,Y) 找图 G 中顶点 Y 的除了邻接点 X 的其他邻接点，若存在则返回顶点号，不存在返回 -1
Get_edge_value(G,X,Y) 获取图 G 中边 (X,Y) 或者 <X,Y>对应的权值
Set_edge_value(G,X,Y) 设置图 G 中边 (X,Y) 或者 <X,Y>对应的权值
Adjacent(G,X,Y) 判断图 G 是否存在边 (X,Y) 或者 <X,Y>

图的遍历

广度优先遍历（BFS）

图的广度优先遍历和树的广度优先遍历（层次遍历）很类似，例如下面的图：

image-20220830012444047

我们选择一个顶点开始进行图的广度优先遍历，例如 A 顶点，第一步将 A 压入辅助队列中，A 出队的时候获取其下一个顶点 B C D 压入队列，依次类推，直到队列为空。但是图和树不同的是，图有可能出现回环，而树不可能，树的结构保证了每个结点都只会被遍历一次，而图如果出现回环那么同一个顶点会被遍历多次，这个时候就需要再定义一个辅助数组，用来记录哪个结点是否被遍历过。

对于不同图的存储方式和不同的图的类型，其广度优先代码略有不同，代码如下所示。

前排说明：请创建一个头文件，名称为图的存储结构.h，代码如下，此头文件需要被使用图的地方进行引用。

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
#pragma once

#include <stdbool.h>
#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS

#define Maxsize 100
#define ElemType int
//邻接矩阵
typedef struct Matrix{
	char Vertex[Maxsize];	//存放顶点的数组
	ElemType Edge[Maxsize][Maxsize];	//存放顶点关系的数组
	int vexnum, arcnum;	//图的总共顶点数和弧的数目
}GMatrix;

/*邻接表法*/
//边，弧
typedef struct ArcNode{
	int adjvex;		//弧指向的结点
	struct ArcNode* next;	//指向下条弧的指针
}ArcNode;

//顶点
typedef struct {
	char data;	//顶点信息
	ArcNode* first;	//第一条边
}VNode,AdjList[Maxsize];

//图
typedef struct {
	AdjList vertices;	//数组存储顶点
	int vexnum, arcnum;	//图的总共顶点数和弧的数目
}GraphAdjList;

邻接矩阵

考虑到需要使用辅助队列完成图的广度优先遍历，需要再创建一个名称为图队列.h的头文件，代码如下：

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
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include "图的存储结构.h"
#define ElemTypeQ int

//队列元素结构
typedef struct node
{
    ElemTypeQ data; //二叉树结点
    struct node* next; //下一个结点的指针
}QNode;

//头结点结点结构
typedef struct head
{
    struct node* front; //队列队头指针
    struct node* rear;  //队列队尾指针
    int size;   //队列的大小
}QHead;


//初始化队列-带头结点
void InitQueue(QHead* q) {
    q->front = NULL;    //队头指针初始化
    q->rear = NULL; //队尾指针初始化
    q->size = 0;    //初始化队列大小
    printf("队列初始化成功\n");
}

//入队操作
bool EnQueue(QHead* q, ElemTypeQ data) {
    QNode* qn = (QNode*)malloc(sizeof(QNode));  //新元素结点申请内存空间
    qn->data = data;
    if (q->size < 1)
    {
        qn->next = NULL;    //尾指针为空
        q->front = qn;  //头指针指向第一个元素
    }
    else {
        qn->next = q->rear->next;   //新元素的下一个元素指针指向队尾指针的下一个
        q->rear->next = qn; //原来的队尾元素指向新队尾元素
    }
    q->rear = qn;   //尾指针指向第一个元素
    q->size++;  //队列的长度+1
    //printf("元素 %d 入队成功,当前队列长度为:%d\n", data, q->size);
    //GetHead(q);
    return true;
}

//出队操作
ElemTypeQ DeQueue(QHead* q) {
    if (q->front == NULL)  //判断队列是否为空
        return NULL;
    QNode* tempNode = q->front;
    ElemTypeQ tempdata = tempNode->data; //获取队头元素
    q->front = tempNode->next;  //队头指向新的队头元素
    free(tempNode); //释放出队元素的内存空间
    q->size--;  //队列元素-1
    return tempdata;    //返回出队元素数据
}

//读取队头元素
ElemTypeQ GetHead(QHead* q) {
    if (q->front == NULL) {
        printf("队列为空队列\n");
        return NULL;
    }  //判断队列是否为空
    printf("队头元素为:%d\n", q->front->data);
    return q->front->data;
}

//销毁队列
bool Destory(QHead* q) {
    for (int i = 0; i < q->size; i++)
    {
        DeQueue(q);
    }
    InitQueue(q);
    printf("队列已销毁\n");
    return true;
}

如下是图的广度优先遍历代码示例：

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
/*邻接矩阵-图*/
#include "图的存储结构.h"
#include "图队列.h"

//初始化图
void InitGraph(GMatrix* g) {
	g->arcnum = 0;	//边数目初始化零
	g->vexnum = 0;	//点数目初始化零
	for (int k = 0; k < Maxsize; k++)
	{
		g->Vertex[k] = 0;	//初始化顶点数组
	}
	for (int i = 0; i < Maxsize; i++)
	{
		for (int j = 0; j < Maxsize; j++)
		{
			g->Edge[i][j] = 0;	//边的关系初始化为零
		}
	}
	printf("图已初始化\n");
}

//在图中插入顶点
bool InsertVertex(GMatrix* g, char v) {
	//判断图是否已满
	if (g->Vertex[Maxsize-1]!=0)
	{
		printf("图已满，无法添加顶点:%c", v);
		return false;
	}
	for (int i = 0; i < Maxsize; i++)
	{
		//如果找到数组值为0 表示可以插入顶点
		if (g->Vertex[i] == 0)
		{
			g->Vertex[i] = v;	//插入新顶点
			printf("顶点:%c 插入图位置:%d 成功", v, i + 1);
			return true;
		}
	}
	printf("出错");
	return false;
}

//创建图
bool CreatGraph(GMatrix* g) {
	/*建立图的顶点和边数*/
	int tempVex =0, tempEdge=0;
	printf("请输入顶点数和边数,例如：2,3(英文的逗号)\n");
	//获取输入的顶点和边数
	scanf("%d,%d", &tempVex, &tempEdge);
	if (tempVex>Maxsize || tempEdge > 10000)
	{
		printf("顶点或者边数超出预定范围\n");
		return false;
	}
	//对图的边数和顶点赋值
	g->vexnum = tempVex;
	g->arcnum = tempEdge;

	/*建立图的顶点信息*/
	tempVex = 0;
	printf("请输入顶点信息\n");
	char tempdata;
	scanf(" %c", &tempdata);
	while (tempdata != '!')
	{
		if (tempVex>=Maxsize || tempVex>g->vexnum-1)
		{
			printf("输入顶点信息超出预定大小\n");
			return false;
		}
		g->Vertex[tempVex] = tempdata;
		tempVex++;
		scanf(" %c", &tempdata);
	}

	/*建立图的边的关系*/
	int index = 0;	//临时指针
	tempVex = 0;	//临时指针
	tempEdge = 0;	//存储输入的数据
	printf("请输入边的信息\n");
	scanf("%d", &tempEdge);
	while (tempEdge != -1)
	{
		if (index > Maxsize-1)
		{
			printf("输入顶点信息超出预定数组");
			return false;
		}
		g->Edge[index][tempVex] = tempEdge;
		tempVex++;
		if (tempVex>g->vexnum-1)
		{
			index++;
			tempVex = 0;
		}
		scanf("%d", &tempEdge);
	}
	printf("图建立完成\n");
	return true;
}

//返回第一个邻接点
int FirstNeighbor(GMatrix* g, int vex) {
	for (int i = 0; i < g->vexnum; i++)
	{
		if (g->Edge[vex][i]==1)
		{
			printf("查找到第一个邻接点为:%c\n", g->Vertex[i]);
			return i;
		}
	}
	printf("未查找到邻接点\n");
	return -1;
}

//返回除了该点的下一个邻接点
int NextNeighbor(GMatrix* g, int vex,int nextVex) {
	for (int i = nextVex+1; i < g->vexnum; i++)
	{
		if (g->Edge[vex][i] == 1)
		{
			printf("查找到第一个邻接点为:%c\n", g->Vertex[i]);
			return i;
		}
	}
	printf("未查找到邻接点\n");
	return -1;
}

//广度优先遍历(BFS)
void BFS(GMatrix* g,int vex) {
	ElemType isSerach[Maxsize];	//辅助数组
	for (int i = 0; i < Maxsize; i++)
	{
		isSerach[i] = 0;	//初始化数组
	}
	QHead q;	//辅助队列
	InitQueue(&q);	//初始化赋值队列
	int tempdata,deqdata;	//临时变量
	EnQueue(&q, vex - 1);	//遍历开始点入队
	isSerach[vex -1] = 1;
	//如果队列不为空，则继续遍历
	while (q.size!=0)
	{
		deqdata = DeQueue(&q);	//出队顶点
		tempdata = deqdata;
		printf("出队顶点为:%c\n", g->Vertex[tempdata]);
		tempdata = FirstNeighbor(g, tempdata);
		if (isSerach[tempdata]==0)
		{
			EnQueue(&q, tempdata);	//压入第一个顶点
			isSerach[tempdata] = 1;
		}
		while (tempdata!=-1)
		{
			tempdata = NextNeighbor(g, deqdata, tempdata);
			if (tempdata != -1 && isSerach[tempdata] == 0)
			{
				EnQueue(&q, tempdata);	//压入第一个顶点
				isSerach[tempdata] = 1;
			}
		}
	}
	printf("图广度优先遍历完成\n");
}


//程序入口
int main() {
	GMatrix g;	//声明图
	InitGraph(&g);	//初始化图
	CreatGraph(&g);	//创建图
	BFS(&g, 4);	//广度优先遍历图
}

测试的图（无向图）示例如下：

image-20220830013902867

我们从顶点 A 开始广度优先遍历，运行结果如下：

image-20220830013948174

其中红框部分表示其的存储矩阵输入，蓝色框表示遍历输出的结果，即 A B E F C D。

当然，你也可以使用有向图来进行测试，例如下图：

image-20220830014209554

当你使用上述有向图进行广度优先遍历的时候，如果是从顶点 A 开始广度优先遍历，则可以得到完整的遍历序列，如果你从 B 开始则会得到不包含 A 的遍历序列，事实上，如果你使用包含多个图的森林来测试上述广度优先算法，也会出现如果没有被指向的顶点被漏掉的情况。

这个时候就需要改进我们的广度优先算法，还记得我们为了避免广度优先遍历多次同一个顶点的时候我们创建了一个辅助数组用来记录每个顶点是否被遍历过吗？这个时候我们就可以继续利用它，遍历这个数组，如果还存在没有被遍历的顶点，则从这个顶点开始，再次进行一次广度优先遍历即可。

邻接表

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
/*邻接表图*/
#include "图的存储结构.h"
#include "图队列.h"
#include <malloc.h>

//初始化图
void InitGraph(GraphAdjList* g) {
	g->arcnum = 0;	//边数初始化为零
	g->vexnum = 0;	//顶点数初始化为零
	for (int i = 0; i < Maxsize; i++)
	{
		g->vertices[i].data = 0;	//顶点数组初始化为零
		g->vertices[i].first = NULL;	//顶点数组初始化为零
	}
	printf("图初始化完成\n");
}

//创建邻接表图
bool CreatGraph(GraphAdjList* g) {
	int tempVex = 0, tempArc = 0;	//声明并初始化两个临时变量
	printf("请输入顶点数和边数,例如：2,3(英文的逗号)\n");
	scanf("%d,%d", &tempVex, &tempArc);	//获取输入的顶点数和边数
	g->vexnum = tempVex;	//顶点数写入图
	g->arcnum = tempArc;	//边数写入图
	printf("请输入顶点信息\n");
	char tempdata;
	tempVex = 0;
	scanf(" %c", &tempdata);	//读取要存储的顶点信息
	while (tempdata != '!')
	{
		//如果超出自己给出的顶点数或者默认的最大顶点数
		if (tempVex >g->vexnum-1|| tempVex >Maxsize)
		{
			printf("超出预定顶点数目\n");
			return false;
		}
		g->vertices[tempVex].data = tempdata;	//读取的顶点信息写入顶点数组
		tempVex++;
		scanf(" %c", &tempdata);
	}

	//头插法插入链表部分
	printf("请输入边表信息，以 -1 表示结束输入\n");
	for (int i = 0; i < g->vexnum; i++)
	{
		scanf("%d", &tempVex);	//读取边表信息
		//头插法建立边信息表
		while (tempVex != -1)
		{
			ArcNode* arcnode = malloc(sizeof(ArcNode));	//创建第一个边
			arcnode->adjvex = tempVex;	//边信息值赋值给创建的边
			arcnode->next = g->vertices[i].first;	//创建的边的下一条指针指向源顶点指向的边
			g->vertices[i].first = arcnode;	//顶点指向第一条边
			scanf("%d", &tempVex);	//读取边表信息
		}
	}
	printf("图建立成功\n");
	return true;
}

//广度优先遍历（BFS）
void BFS(GraphAdjList* g,int vex) {
	int isSerach[Maxsize];	//声明辅助数组
	for (int i = 0; i < Maxsize; i++)
	{
		isSerach[i] = 0;	//初始化辅助数组
	}
	QHead q;	//声明队列
	InitQueue(&q);	//初始化辅助队列

	EnQueue(&q, vex - 1);	//第一个顶点入队
	isSerach[vex - 1] = 1;	//表示第一个顶点已经遍历过了

	ElemTypeQ data = 0;
	ArcNode* tempnode;
	while (q.size!=0)
	{
		data = DeQueue(&q);	//出队操作
		printf("顶点 %c 已出队\n", g->vertices[data]);
		tempnode = g->vertices[data].first;
		while (tempnode!=NULL)
		{
			//如果这个顶点没有被遍历过
			if (isSerach[tempnode->adjvex]!=1)
			{
				EnQueue(&q, tempnode->adjvex);	//入队下一个顶点
				isSerach[tempnode->adjvex] = 1;	//表面该顶点已经被遍历了
			}
			tempnode = tempnode->next;
		}
	}
	printf("广度优先遍历图完成\n");
}

//程序入口
int main() {
	GraphAdjList g;
	InitGraph(&g);
	CreatGraph(&g);
	BFS(&g, 1);	//从图中顶点 A 位置开始广度优先遍历
}

如果以下图顶点 A 位置开始广度优先遍历，运行结果如下：

image-20220830014209554 image-20220830033428161

同样的，邻接表创建的无向图也可以使用上述代码进行广度优先遍历，当然，代码依旧存在对于如果没有入度的顶点无法遍历到的情况，解决办法和邻接矩阵部分一样，额外定义遍历辅助数组，查看辅助数组中是否存在未遍历的顶点，如果有，就以该顶点为广度优先遍历的起点开始遍历。

广度优先生成树

因为广度优先遍历会产生一定的遍历次序，所以可以通过广度优先遍历生成一颗对应的广度优先生成树，图示如下：

image-20220830034207729

深度优先遍历（DFS）

深度优先遍历类似于树的“深度优先遍历”，例如下图，如果在 A 开始深度优先遍历，则会先获取 A 点的数据，然后遍历 A 的第一个链接的顶点 E ，获取第一个链接的顶点 E 的数据，然后再遍历 E 的第一个链接的顶点，如果不为空，则继续向下遍历获取数据，直到其子顶点为NULL，则会遍历其父顶点的另一个子顶点。

你会发现它的逻辑其实就是递归遍历，由于图的性质，在实现的时候依旧需要使用辅助数组来标识哪个顶点被遍历过。

image-20220830192941014

邻接矩阵

现在来邻接矩阵实现深度优先遍历，首先需要声明一个全局变量int isSerach[Maxsize];用来做辅助数组，记得在使用深度优先遍历前将辅助数组初始化为 0 ，表示顶点没有被访问过。

如下代码只需要放在上面邻接矩阵的广度优先遍历方法的下面即可。

1
2
3
4
5
6
7
8
9
10
11
12
//深度优先遍历
void DFS(GMatrix g, int vex) {
	printf("遍历顶点:%c\n", g.Vertex[vex]);
	isSerach[vex] = 1;	//标识已经遍历过顶点
	for (int i = 0; i < g.vexnum; i++)
	{
		if (g.Edge[vex][i]==1 && isSerach[i] !=1)
		{
			DFS(g, i);
		}
	}
}

测试代码：

1
2
3
4
5
6
7
8
9
10
11
//程序入口
int main() {
	GMatrix g;	//声明图
	InitGraph(&g);	//初始化图
	CreatGraph(&g);	//创建图
	for (int i = 0; i < Maxsize; i++)
	{
		isSerach[i] = 0;	//初始化辅助数组
	}
	DFS(g, 0);	//深度优先遍历邻接矩阵图 从顶点 A 开始
}

测试图如下，从下图的顶点 A 开始深度优先遍历。

image-20220830192941014

运行结果：

image-20220830195702611

同样的，如果图中存在顶点不存在入度，或者是森林图的情况，则需要另外声明一个函数来遍历辅助数组，查看哪个顶点还未被遍历过，对未被遍历过的顶点进行再次的深度优先遍历。

邻接表

如下深度优先遍历方法代码只需要在前面广度优先遍历的邻接表的.c文件中添加到最后即可。但是仍需创建一个全局变量int isSerach[Maxsize];，用来做辅助数组，记得在执行深度优先遍历前将辅助数组初始化为0，即

1
2
3
4
for (int i = 0; i < Maxsize; i++)
{
	isSerach[i] = 0;	//初始化辅助数组
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//深度优先遍历
void DFS(GraphAdjList g,int vex) {
	printf("当前顶点为：%c\n", g.vertices[vex].data);
	isSerach[vex] = 1;
	ArcNode* arcnode = g.vertices[vex].first;	//临时顶点
	while (arcnode!=NULL)
	{
		if (isSerach[arcnode->adjvex]!=1)
		{
			DFS(g, arcnode->adjvex);
			arcnode = arcnode->next;
		}
	}
}

测试代码：

1
2
3
4
5
6
7
8
9
10
11
//程序入口
int main() {
	GraphAdjList g;	//声明图
	InitGraph(&g);	//初始化图
	CreatGraph(&g);	//创建图
	for (int i = 0; i < Maxsize; i++)
	{
		isSerach[i] = 0;	//初始化辅助数组
	}
	DFS(g, 0);	//对图从顶点 A 进行深度优先遍历
}

测试图如下，从下图的顶点 A 开始深度优先遍历。

image-20220830192941014

运行结果:

image-20220830194024910

同样的，如果图中存在顶点不存在入度，或者是森林图的情况，则需要另外声明一个函数来遍历辅助数组，查看哪个顶点还未被遍历过，对未被遍历过的顶点进行再次的深度优先遍历。

深度优先生成树

同广度优先生成树，随着深度优先的遍历顺序，可以对应的生成一棵深度优先生成树。

最小生成树

生成树的理解如下图，左边的图可以产生如右边的两种生成树（当然不止这两种），其生成树的特点是连通的，且边数目等于顶点数目 -1.

image-20220830200438476

最小生成树是在如上的基础上，边存在权值，如果生成树的边权值之和最小的树，被称为最小生成树。

获取最小生成树的算法有两种：

  • Prim（普利姆）算法

    从图中某个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

  • Kruskal（克鲁斯卡尔）算法

    每次选择一条权值最小的边，使得这两条边的两头联通，直到所有的结点都连通。

最短路径

最短路径问题，直接用应用带入，例如我们的导航是如何直到我们和目的地之间的最优最短路径呢？

关于最短路径问题可以分为如下情况：

  • 单源最短路径
    • BFS 算法（无权图）
    • Dijkstra 算法（带权图，无权图）
  • 各顶点间的最短路径
    • Floyd 算法（带权图，无权图）

BFS 算法

BFS 也就是广度优先遍历算法，可以求得无权图（或者说权都为 1）的图的单源最短路径。

实现思路和广度优先遍历无差别，只是在广度优先遍历在读取结点数据的时候需要做两个操作，创建两个数组，分别表示遍历开始顶点到当前顶的距离和表示自己上一个最近的顶点是谁。在每次广度优先遍历顶点的时候，将两个数组进行相关赋值操作，遍历完成后，两个数组就包含了当前广度优先遍历顶点到其他顶点的最短路径信息。

此处用邻接矩阵来做代码示例：

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
//广度优先-最短路径
void BFS_Min_Distance(GMatrix* g,int vex) {
	ElemType path[Maxsize];	//记录上一个顶点
	ElemType d[Maxsize];	//记录顶点间的距离
	ElemType isSerach[Maxsize];	//辅助数组
	for (int i = 0; i < Maxsize; i++)
	{
		isSerach[i] = 0;	//初始化数组
		path[i] = -1;
		d[i] = -1;
	}
	QHead q;	//辅助队列
	InitQueue(&q);	//初始化赋值队列
	int tempdata, deqdata;	//临时变量
	EnQueue(&q, vex - 1);	//遍历开始点入队
	isSerach[vex - 1] = 1;
	d[vex - 1] = 0;
	//如果队列不为空，则继续遍历
	while (q.size != 0)
	{
		deqdata = DeQueue(&q);	//出队顶点
		tempdata = deqdata;
		printf("出队顶点为:%c\n", g->Vertex[tempdata]);
		tempdata = FirstNeighbor(g, tempdata);
		if (isSerach[tempdata] == 0)
		{
			EnQueue(&q, tempdata);	//压入第一个顶点
			isSerach[tempdata] = 1;
			d[tempdata] = d[deqdata] + 1;
			path[tempdata] = deqdata;
		}
		while (tempdata != -1)
		{
			tempdata = NextNeighbor(g, deqdata, tempdata);
			if (tempdata != -1 && isSerach[tempdata] == 0)
			{
				EnQueue(&q, tempdata);	//压入第一个顶点
				isSerach[tempdata] = 1;
				d[tempdata] = d[deqdata] + 1;
				path[tempdata] = deqdata; 
			}
		}
	}
	printf("图广度优先遍历完成\n");
}

Dijkstra 算法

Dijkstra（迪杰斯特拉）算法是一种可以求带权图的最短路径的算法，例如下面的图：

image-20220830221648062

该算法需要创建 3 个数组，其作用如下：

  • final[]：记录顶点是否被连通了。
  • dist[]：记录顶点关于已连通路径的权值。
  • path[]：记录顶点和算法开始遍历顶点（单源）的路径，实际上是记录和最近上一个顶点。

例如，我们从顶点 A 开始算法遍历，首先需要进行数组初始化，初始化结果如下：

image-20220830222508474

上述 A 顶点的final[]的True表示顶点 A 是目前连通路径中，因为只有一个True，所以它是目前连通路径的唯一顶点，也是初始顶点，而dist[]中的权值表示从顶点 A 到 A 可以直接连通的顶点的权值（带权路径长度），由图可知，顶点 A 和其他顶点都存在通路，所以 BCDE 的dist[]的值是顶点 A 到它们的路径权值，而path数组表示从顶点 A 到其中的任何一个顶点的路径（当前顶点的上一个路径）。

完成上面的初始化工作后，现在开始遍历dist[]数组，找到其中dist[]数值最小的（即权值最小）的，让它成为最短（即结果）路径的一个顶点，即顶点 E 。然后再做类似于初始化的工作，得到的数组结果如下：

image-20220830223723290

数组final[]将顶点 E 的数值修改为True表示顶点 E 已经是最短路径中的一个顶点了，这个时候以顶点 E 为开始，计算从 E 到和它连通的顶点的权值和顶点 A 到它的权值和是否比 A 到其他顶点的权值低，如 C 顶点到 E 的权值为 1 ，A 到 C的原先权值为 3 ，如果从 A 到 E 再到 C 的权值则为 $3+1=4$ 比 A 到 C 的权值高，则不覆盖 C 的dist[]值，而与 E 连通的另一个顶点 D 同样的，如果 A 到 E 再到 D 的权值为 $3+6=9$，而其值比 A 到 D 的权值高，所以也不覆盖，然后从中选取权值最低的 C 作为新的顶点，依次类推。

Floyd 算法

关于 Floyd 算法其思路可以参考 求最短路径Floyd算法！

这个算法就算录视频说明也要说上一阵，不想打字了，自行参考吧 :）

算法的示例代码如下：

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
//Floyd 算法
void Floyd(GMatrix g) {
	int path[Maxsize][Maxsize];
	for (int i = 0; i < Maxsize; i++)
	{
		for (int j = 0; j < Maxsize; j++)
		{
			path[i][j] = -1;
		}
	}
	for (int k = 0; k < g.vexnum; k++)
	{
		for (int i = 0; i < g.vexnum; i++)
		{
			for (int j = 0; j < g.vexnum; j++)
			{
				if (g.Edge[i][j]> g.Edge[i][k]+ g.Edge[k][j])
				{
					g.Edge[i][j] = g.Edge[i][k] + g.Edge[k][j];
					path[i][j] = k;
				}
			}
		}
	}
}

注：算法是在邻接矩阵存储格式下实现的

拓扑排序

拓扑排序适用于 DAG 图（Directed Acyclic Graph），即有向无环图。人话来说就是图中不能出现回环。

拓扑排序可以解决下图的顺序问题：

image-20220831003334997

图片来源：王道《数据结构》

拓扑排序可以解决上述 AOV 网（Activity On Vertex Network）的执行顺序问题。其解决方案：

AOV 人话来说就是用顶点来表示一个个的事件/活动

  1. 从 AOV 网中选择一个没有前驱（入度为 0 ）的顶点并输出
  2. 从网中删除该顶点和所有以它为起点的有向边
  3. 重复上述操作，直到当前 AOV 网为空 或者 当前网中不存在无前驱的顶点为止

拓扑排序代码示例如下：

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
//拓扑排序
void Topological(GMatrix g) {
	QHead q;	//声明辅助队列
	InitQueue(&q);	//初始化队列
	for (int j = 0; j < g.vexnum; j++)
	{
		for (int i = 0; i < g.vexnum; i++)
		{
			if (i==g.vexnum-1 && g.Edge[i][j]==0)
			{
				EnQueue(&q, j);	//将无入度的顶点入队
				for (int k = 0; k < g.vexnum-1; k++)
				{
					g.Edge[j][k] = 0;	//将关于无入度的顶点删除边
				}
			}
		}
	}
	printf("顶点数据为:");
	//队列不为空，则弹出队列内容
	while (q.size!=0)
	{
		printf("%c", g.Vertex[DeQueue(&q)]);
	}
}

将代码放在广度优先求最短路径算法下面即可，代码以图的邻接矩阵存储结构实现的。

使用的图示例如下：

image-20220831011251475

运行结果：

image-20220831011032498

End

图学完啦，学完图就没有其他的数据结构了，剩下就是如何来利用这些数据结构来应用了，比如查找和排序。

image-20220831013625512