数据结构与算法（Python版）第2版 课件 chap9 图的应用

第9章图的应用最小生成树构造连通图的最小代价生成树称为最小生成树。最小生成树实现算法：克鲁斯卡尔（Kruskal）算法普里姆（Prim）算法。2最小生成树1.克鲁斯卡尔（Kruskal）算法设无向连通图为G＝(V,E)，令G的最小生成树为T＝(U,TE)，其初态为U＝V，TE＝{}，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

图(a)按照Kruskal算法构造最小生成树的过程如图(b)到图(f)所示。在构造过程中，按照图中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个节点的生成树，有n-1条边，故反复上述过程，直到选取了n-1条边为止，就构成了一棵最小生成树。3最小生成树4最小生成树2.普里姆（Prim）算法假设图G＝(V,E)中V为图中所有顶点的集合，E为网图中所有边的集合。设置两个新集合U和T，其中集合U存放G的最小生成树的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U＝{v1}（假设构造最小生成树时，从顶点v1出发），集合T的初值为T＝{}。5最小生成树从所有u∈U，v∈V－U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U＝V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。从顶点v1出发，最小生成树的生成过程：(b)→(c)→(d)→(e)→(f)。

Prim算法示意图6最小生成树Prim算法可用下述过程描述:步骤1：算法从U={v1}(v1∈V)，T={}开始。步骤2：在所有u∈U，v∈V-U的边(u,v)∈E中找一条代价最小的边(u,v)步骤3：(u,v)并入集合T，同时v并入U步骤4：重复步骤2和步骤3，直到U=V为止。此时T中必有n-1条边，则(V,T)为N的最小生成树。为实现这个算法需要附设一个辅助数组closedge，记录从U到V-U具有最小代价的边，对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，它包括两个域，其中lowcost存储该边上的权。显然，closedge[i-1].lowcost=min{cost(u,vi)|u∈U}。用Prim方法建立有n个顶点的邻接矩阵存储结构的图G的最小生成树代码如下所示，建立的最小生成树存于数组closevertex中：7最短路径最短路径是指两个顶点（源点到终点）之间经过的边上权值之和最少的路径。下面介绍两种计算最短路径算法：迪杰斯特拉(Djikstra)算法佛洛伊德（Floyd）算法。 8最短路径1.迪杰斯特拉(Djikstra)算法迪杰斯特拉算法并非一下子求出起始点到结束点的最短路径，而是一步步求出它们之间顶点的最短路径，即基于已经求出的最短路径，逐步求得更远顶点的最短路径，最终达到目的。通过Dijkstra计算图G中的最短路径时，需要引进两个集合S和U。其中，集合S用于存放已求出最短路径的顶点（以及相应的最短路径长度），集合U用于存放还未求出最短路径的顶点（以及该顶点到起点的距离）。

9最短路径迪杰斯特拉算法具体步骤包括：步骤1：初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离，若s和v不相邻，则距离为∞。步骤2：从U中选出距离最短的顶点k，并将顶点k加入到S中；同时，从U中移除顶点k。步骤3：更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而借助中间定点后的距离可能小于两顶点的直接距离，即(s,k)+(k,v)可能小于(s,v)。步骤4：重复步骤步骤2和步骤3，直到遍历完所有顶点。

10最短路径【解析】以顶点d为起点，迪杰斯特拉算法执行过程如图3.33所示。第1步，如图（a）所示。S={d(0)}U={a(∞),b(∞),c(3),e(4),f(∞),g(∞)}(a)第2步，如图（b）所示。选取顶点cS={d(0),c(3)}U={a(∞),b(∞),e(4),f(∞),g(∞)}(b) 11最短路径

第3步，如图（c）所示。选取顶点eS={d(0),c(3),e(4)}U={a(∞),b(13),f(6),g(12)}(c) 第4步，如图（d）所示。 选取顶点f S={d(0),c(3),e(4),f(6)} U={a(22),b(13),g(12)} (d)

12最短路径 第5步，如图（e）所示。 选取顶点g S={d(0),c(3),e(4),f(6),g(12)} U={a(22),b(13)} (e) 第6步，如图（f）所示。 选取顶点b S={d(0),c(3),e(4),f(6),g(12),b(13)} U={a(22)} (f) 13最短路径 第7步，如图（g）所示。 选取顶点a S={d(0),c(3),e(4),f(6),g(12),b(13),a(22)}(g)

14最短路径2.佛洛伊德（Floyd）算法迪杰特斯拉算法是计算一个节点到其他顶点的最短路径，而弗洛伊德算法是一次求出任意两点间的最短路径。佛洛伊德通过不断加入中间定点迭代计算处任意两点间的最短路径。弗洛伊德算法的基本思想如下所示：以计算vi到vj的最短路径为例，如果从vi到vj有边，则从vi到vj存在一条长度为wij的路径，但该路径不一定最短，假如在此路径上增加一个节点v0，如果（vi,v0,vj）存在，且（vi,vj）大于（vi,v0,vj）的路径长度，则（vi,v0,vj）为vi到vj间的最短路径；假如再增加一个顶点v1，如果（vi,v0,v1,vj）小于（vi,v0,vj），则（vi,v0,v1,vj）为vi到vj的最短路径；依次类推，在经过n次比较，便可获得从vi到vj的最短路径。

15最短路径

16最短路径

17

最短路径

18

最短路径

19

最短路径

20

最短路径

21

最短路径

22

最短路径

23

图论在AI中应用（1）知识图谱1）结构表示：知识图谱是一种大规模的语义网络，用于表示知识和实体之间的关系。它本质上是一个图，其中实体是顶点，实体之间的关系是边。例如，在一个医学知识图谱中，“疾病”和“药物”是实体（顶点），“治疗”是一种关系（边），可以表示某种疾病可以用某种药物治疗。2）推理和问答系统：利用图的遍历和路径搜索算法，在知识图谱中进行推理。例如，对于用户的问题“某种疾病可以用什么药物治疗”，系统可以通过在知识图谱中查找从表示该疾病的顶点到表示药物的顶点的路径，来提供答案。24

图论在AI中应用（2）神经网络架构1）架构理解：在一些复杂的神经网络架构中，如Transformer架构，可以用图来表示神经元之间的连接关系。将神经元看作顶点，神经元之间的连接看作边，这样可以更好地理解神经网络的信息流动和计算过程。2）信息传播和更新：GNNs利用图的结构特点，通过在图上传播和更新节点信息来进行学习。例如，在节点分类任务中，节点的特征信息会根据其邻居节点的特征在图上进行传播和更新，从而使每个节点能够学习到更丰富的表示，提高分类性能。25

图论在AI中应用（3）强化学习中的环境建模1）环境表示为图：在一些复杂的强化学习场景中，如机器人路径规划、游戏等，环境可以用图来表示。例如，在机器人在一个房间内移动的场景中，房间的不同位置可以看作顶点，机器人可以移动的路径看作边。2）策略学习和路径规划：通过在图表示的环境中进行搜索和探索，智能体（如机器人）可以学习到最优的策略。例如，在马尔可夫决策过程（MDP）中，智能体根据图的结构和状态转移概率，通过价值函数和策略梯度等方法来学习在环境中采取最佳行动的策略。26AI对图论影响（1）大数据和复杂网络促使图存储和计算方法改进随着AI