[数据结构与算法]【数据结构】图

图的存储结构

节点之间是多对多的联系，导致了图没有顺序的存储结构，也很难表示图的前后元素

邻接矩阵

可以使用二维数组形式的邻接矩阵来表示元素间的关系

顶点表（记录各个顶点信息）

定义一个从0到n-1的数组，将v1~vn放入这个数组中

这个顶点表的作用就是，通过一次遍历就能拿到顶点的下标，这个下标和二维数组中的下标位置对应

邻接矩阵（表示各个顶点间的关系）

定义一个二维数组，如果两个顶点之间有边，则对应位置上的值为1

这也就导致了无向图的邻接矩阵是对称的（v1和v2算一条边，v2和v1算一条边，自身和自身无边）

不过有向图只用存储出度边，比如v1->v2，只用在一行二列上记为1

带权有向图和有向图大致相同，区别在于记录的值为权值，而其他的边设置为无穷大

多重链表

常用邻接表、邻接多重表、十字链表来表示

可以说多重链表的核心是邻接表，另外两个是一种优化

邻接表

同样需要负责存储顶点的结构，作用同样是可以获取到下标的位置

创建邻接表中，边结构的时候，通过对总边数次数的循环，一次循环中输入v1,v2，并通过遍历存储顶点的数组拿到这两个点的下标 i 和 j 。i 对应的就是出度边，而 j 就是需要创建的入度结点。

需要注意，邻接表适用于求出度，即使是逆邻接表也只适用于求入度，而这个邻接表本身并不适合求总的结点度数

十字链表

十字链表解决邻接表的有向图问题

由于邻接表只能求出度 / 入度边，所以：

• 为存储顶点的数组结构新增加一个指针域，这个指针域指向它的入度边
• 为每一个弧边的数据结构增加
  1. 具有相同头节点的信息
  2. 具有相同尾结点的信息（出度边为尾结点，作用和邻接表中的nextarc相同）

分析一下：

1. 以a为尾结点，可以指向b,c，所以最上面a的tlink指针指向的是(0,1),(0,2)
2. 再以a为头节点，有c,d指向a，所以a的hlink指针指向(2,0),(3,0)
3. a看完了，再看b。b没有出度边，所以tlink直接为NULL
4. 有a,d可以指向b，所以b的hlink指针指向(0,1),(3,1)…

邻接多重表

邻接多重表解决邻接表的无向图问题

邻接表可以很容易找到顶点和边相关的信息，但是删除某一条边需要找到这条边上的两个结点

即，任何一条边都会出现两次，要删除某一条边需要进行两次删除

分析一下：

1. 看v1，可以指向v2, v4，所以最上面a的 ilink 指针指向的是(0,1)，弧的ilink继续指向(0,3)
2. 看v2，相关联的有v1, v3, v5，但是之前已经建立了v1->v2的连接，所以这里是v2的tlink指针指向(0,1)————(v2->v1)，同样是弧的 jlink 继续指向 (2,1) 和 (4,1)
3. 看v3，相关联的有v2, v4, v5，但是之前已经建立了v2->v3的连接~~，所以是v3的jlink~~。更正：之前是已经建立了v1->v2的连接，所以v2和v1连接的时候使用的是jlink，所以后面分别建立的是v3->v2，v5->v2的tlink相同的连接。而这里建立的是使用hlink建立v3->v2的联系
4. 看v4，相关联的有v1, v3。前面有由v1->v4建立的hlink连接，所以这里只能指向tlink连接
5. 看v5，相关联的有v2, v3 …这里使用的是hlink连接

图的遍历

图中可能存在回路，且图的任一顶点都可能和其他顶点相通，所以在访问完某个顶点后可能又会沿着某些边回到了曾经访问过的顶点。

DFS

概念

为了解决这个问题，我们需要设置一个辅助数组visitedd[n]来标记每个被访问过的顶点

• 在访问某一个起始顶点v后，由v出发，访问它的任一邻接顶点w1
• 再从w1出发，访问与w1邻接但还未被访问过的顶点w2
• 重复前两步，直到所有的邻接顶点都被访问过为止
• 接着回退到上一次访问的顶点，看看还有没有没被访问过的
  • 有，重复第一步、第二步
  • 没有，继续回退

邻接矩阵算法实现

首先创建一个邻接矩阵，和一个辅助数组，初始的时候辅助数组的值设为0

假设我们从结点2开始遍历：

• 首先visited[1]会变为1，判断邻接矩阵的第二行：| 1 ↓ | 0 | 0 | 0 | 1 | 0 |，发现结点一没有被遍历过，visited[0]变为1
• 现在看第一行 | 0 | 1↓ | 1 | 1 | 0 | 0 |，判断辅助数组，结点2已经被访问过，指针后移
  • | 0 | 1 | 1 ↓ | 1 | 0 | 0 |，将节点三的visited[2]变为1
• 现在去第三行 | 1↓ | 0 | 0 | 0 | 1 | 0 |，判断辅助数组，结点1已经被访问过，指针后移
  • | 1 | 0 | 0 | 0 | 1↓ | 0 |，将结点五的visited[4]变为1
• 现在去第五行| 0 | 1↓ | 1 | 0 | 0 | 0 |，判断辅助数组，结点2已经被访问过，指针后移
  • | 0 | 1 | 1↓ | 0 | 0 | 0 |，判断辅助数组，结点3已经被访问过，指针继续向后遍历，发现没有边可以走了，于是回退
• 第三行不行 继续回退
• 第一行发现节点四未被访问过，将结点四的visited[3]变为1…

最后BFS遍历顺序为2->1->3->5->4->6

现在我们将这个思路转换成代码

void DFS(Graph G, int v){	// 邻接矩阵G
	printf("%d",v);
	visited[v] = true;	// 访问第v个顶点
	for(int length = 0; length < G.vexnum; length++){
		// 如果没有被访问过，且从第一列开始指针向后移动遇到1
		if((G.arcs[v][length]!=0)&&(!isvisited[length])){
			// length是v的邻接点，如果length未被访问就递归DFS
			DFS(G, length);
		}
	}
}

BFS

概念与算法实现

同样是使用visited数组表示是否遍历过，遍历的方法和树采用队列的BFS一致。

void VFS(Graph G, int v){
	printf("%d",v);
	visited[v] = true;	// 访问第v个顶点
	// 初始化辅助队列
	initQueue(Q);
	// 将首结点入队
	Enqueue(Q,v);
	// 当队不为空时
	while(!QueueEmpty(Q)){
		Dequeue(Q,u);
		// 出队，并判断u的邻接点
		// 首先找到邻接表中，u左边的数组的哪个位置，然后去后方的拉链找它的邻接点
		for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G,u, w)){
			if(!visited[w]){
				printf("%d",w);
				visited[w] = true;
				// 将邻接点入队
				Enqueue(Q,w);
			}
		}
		
	}
}

图的应用

最小生成树

性质

将有回路的图转换为一颗树

生成树是图的极小连通子图：所有顶点都可以走到，并且没有回路，如果去掉一条边则非连通。

故n个顶点的连通图的生成树有n-1条边，如果再加一条边就会生成回路。

而含有n个顶点n-1条边的图不一定是生成树，因为他不满足连通的条件，可以像森林一样拆成多个部分。

上面是生成树的概念，最小生成树是根据一个带权无向网，生成一颗各边权值之和最小的那棵树，也叫最小代价生成树。

现在我们看看如何去构造一颗最小生成树

普利姆算法

假设所有顶点集合为V

生成树上顶点集合为U

首先向U中放入一个元素，然后在U-V中找到这两个集合之间所有连线最短的那个情况，将U-V中的点放入U中

由于它的每一个顶点都要找其他的点进行判断，所以时间复杂度为o(n^2)

克鲁斯卡尔算法

将图中所有的边先都去掉，形成n个顶点而无边的非连通图T=( V, {} )

然后贪心的向边中加入权值较小的（由于最小生成树不能形成环，所以如果加入某条边后会形成环，就不加入这条边）

由于选择边和顶点数没关系，所以与边的从小到大排序有关，其中采用堆排序为O(eloge)

最短路径

和最小生成树不同，最短路径问题不需要找到所有点之间的距离，它只需要判断某两个顶点之间的最短距离

迪杰斯特拉算法（单源最短路径）

1. 初始化：令S = { v0 }，T = { 其余顶点 }
2. 先找出从源点v0到各个终点vk的直达路径(v0, vk)，如果一条边可以直达，就记录权值，否则为∞
3. 选出最小距离的点，加入到S中
4. 重复第二、第三步，直到S = 全部顶点为止

举例

计算出v0到其他各个点之间的最短路径

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V4akxctE-1653908737699)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203200859831.png)]

首先将v0放入S集合中，判断它到其他各个点之间的直达距离。如果可直达就记录权值，否则记为∞

这里v0直达为{v2, v1, v4, v6}；然后在这些直达路径里面选出最短的那个，并将连接的点加入S集合中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EKHdV1Ua-1653908737700)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203200902277.png)]

加入v2后，v0可以通过v2到其他顶点了

比如之前v0无法直达v3，但是通过v2中转可以到达v3

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e5PXf0Ca-1653908737701)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203200904639.png)]

然后继续选择最短的路径，并将最短路径上的点加入S集合中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6VL1J4xb-1653908737703)(…/AppData/Roaming/Typora/typora-user-images/image-20220320090636946.png)]

…

最终结果如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SJF3uknT-1653908737704)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203200907241.png)]

弗洛伊德算法（所有顶点间的最短路径）

1. 逐个顶点试探
2. 从vi到vj的所有可能存在的路径中选出一条长度最短的路径
3. 重复第一第二步

举例（待看课本）

有向无环图及其应用

有向无环图指的是，从某个顶点出发以后，最后无论怎么走都不会回到这个点

• AOV网用于解决拓扑排序问题

• AOE网用于解决关键路径问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1nNCHsDa-1653908737705)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203200941340.png)]

拓扑排序

AOV网中不允许有回路，因为如果有回路存在，就说明某项活动以自己为先决条件，这是荒谬的

以一张排课表举例，将上的课程作为活动，边作为先修条件关系

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iex9pUV9-1653908737707)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203200943072.png)]

C1, C2, C3, C4, C5, C7, …

在AOV网没有回路的前提下，我们将全部活动排成一个线性序列，使得AOV网中如果有弧<i, j>存在，则在这个序列中，i 一定排在 j 的前面，具有这种性质的线性序列成为拓扑有序序列，相应的拓扑有序算法成为拓扑排序。

拓扑排序的方法：

1. 在有向图中选一个没有前驱的顶点且输出
2. 将以该点为尾结点的弧全部删掉
3. 重复第一步第二步

如果最后的结果存在剩余的点，找不到没有前驱的结点，则说明这个AOV网存在环

关键路径

• 以顶点表示事件的开始或是结束
• 边表示活动的事件，弧的权表示活动持续的时间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qxUTTuJ4-1653908737708)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201026803.png)]

对于AOE网我们需要关心两个问题：

1. 完成这个工程至少需要多少时间
2. 哪些活动是影响工程进度的关键

关键路径指的是路径长度最长的路径

确定关键路径需要定义4个描述量：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BKZqHQ2C-1653908737709)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201032521.png)]

根据这四个描述量我们可以知道

l(i) - e(i) 表示完成活动ai的时间余量

有一些活动是没有时间余量的，即i(i) == e(i)，这表示活动最早开始时间 == 最迟开始时间，由于不能推迟，所以为关键活动

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aDQd63L2-1653908737710)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201039377.png)]

举例

最早发生时间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yWMDQ6qa-1653908737711)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201044316.png)]

如果vj后面还有很多的活动等待进行，必须得先等待vj前面的任务全部都执行完毕，所以要等到前面耗时最长的任务都执行完毕了以后，才能继续执行后面的，故vj的最早执行时间Ve(Vj) = 88

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kiatsFM4-1653908737712)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201047490.png)]

同理，这里也是选最大的当最早开始时间。

最迟发生时间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7sPNionn-1653908737714)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201049441.png)]

而最迟发生时间，是选择最少值：

比如这里，已知vn最迟在10的时候发生，那么vl(vj)应该为10 - 7 = 3，因为只有这样才能确保在10的时候，完成所有以vj开始的任务。

所以，最早发生时间要等前面全部执行完毕以后才会执行，选时间长的

最晚发生时间要选时间短的，又由于最晚发生时间由后面确定，所以是在计算完最早发生事件后，倒推来计算的

求v

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PuJyHGZm-1653908737715)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201054823.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yEYMKMcZ-1653908737716)(https://gitee.com/nekojimmy/kuriasuna_img-bed/raw/master//202203201057224.png)]

求e

e的最早发生时间，由有向弧的弧尾值决定

e的最晚发生时间，由弧头减去权值决定

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HTiHxMTQ-1653908737716)(…/AppData/Roaming/Typora/typora-user-images/image-20220320105928787.png)]

最后选出 l - e ==0的所有弧作为关键路径

一些概念

• 完全图：每个顶点之间都有边
• 邻接矩阵多用于稠密图，邻接表多用于稀疏图