图及应用二.ppt

1、第五课和应用2，图中的几个茄子典型算法，最小生成树最短路径拓扑排序关键路径，示例1，最佳工程成本描述城市地图，图中顶点表示城市，无向边缘表示两个城市之间的连接关系，边缘的权利是在两个城市之间建设高速公路的成本。研究结果表明，牙齿地图上有一个茄子特征，即任重而道远。现在的问题是，建设多条高速公路，连接所有城市，询问如何设计，将工程的总成本降至最低。1 .确保已连接配置的地物。2.为了最小化成本，图中没有环。3.图中所有边的权重之和最小。这就是我们想要的结果。这些问题可以概括为图的最小生成树问题。如果地物是连接的无方向图或强烈连接的方向图，如果地物是具有根的方向图，则还可以调用一次DFS或bfs，

2、从根开始系统地访问所有顶点。在牙齿情况下，图中所有顶点加上遍历过程中经过的边的子图形称为原始图中的生成树。对于与未连接的无方向图没有强烈连接的方向图，如果有根或从根外部的顶点开始，则调用一次bfs或DFS后，通常不能系统地访问所有顶点。只能得到基于起点的连接分支(或强连接分支)的生成树。要访问其他顶点，必须找到未访问的顶点上的顶点，然后重新调用bfs或DFS以生成森林。1 .图的生成树是什么，图的生成树，连接图(强连接图)的生成树有三个茄子条件。(1)顶点是图形中的所有顶点。(2)边是图的部分角，连接了图的所有顶点，(3)不构成循环，表明图的生成树不是唯一的。具有n个顶点的权重连接图可以证明相

3、应生成树具有边。n-1，2。图的最小生成树是什么，权重最小的生成树(图中称为最小生成树)是什么？下面的(b)、(c)、(d)是图(a)中的生成树，权重分别为20、33和19，前两个不是最小生成树，只有图(d)是最小生成树。具有N个顶点的权重连接图形，在相应的跨度树中有n-1个角！那么到底选择哪个n-1页呢？想想：3。寻找最小生成树的方法，核心：选择哪个n-1边，方法1:基于搜索的两个算法，深度优先遍历，宽度优先遍历，结论：要最小化权重总和，如果顶点数和边数很大，那么需要搜索所有情况，各位，有更好的方法吗？方法2:贪心的两个茄子算法、Prim算法、Kruskal算法、Prim算法、1、Prim算

4、法的基本思想：顶点的集合s和边的集合TE、s和TE的初始状态都是空集合。选择地物中的顶点K以从K开始生成最小生成树，并将K添加到集合S。重复操作，直到选择N-1边。选择权重最低的边(x，y)之一。其中XS，not(ys)；将顶点y添加到集s，将边(x，y)添加到集te。得到最小生成树T=(S，TE)。练习：创建使用Prim算法实现最小生成树的上图的过程？如何证明Prim算法的正确性？提示：使用反证法。操作沿边执行，因此数据结构必须使用边集阵列表示。从文件中读取图形的邻接矩阵g。readln(n)；for I :=1 to n do for j 3360=1 to n do read(gi，j)；边集阵列TE，s是图形的顶点初始化。For i:=1 To n do si:=falseS1:=真；g weight 3360=0；通过最小生成树的加权和2，Prim算法的实现，得出最小生成树的n-1边。for I :=1 to n-1 do begin min :=maxint；选择For j:=1 to n do权重最低的边(x，y)之一。其中xS