7.5.4Prim算法

普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在生成树中的顶点（假设为 A 类），剩下的为另一类（假设为 B 类）。

对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

假如从顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RGoQ502l-1637250894597)(https://www.zhihu.com/equation?tex=V_0)] 出发，顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LJwwdbMe-1637250894598)(https://www.zhihu.com/equation?tex=V_1)] 、[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-inYCsUdQ-1637250894600)(https://www.zhihu.com/equation?tex=V_5)] 的权值分别为3、4，所以对于顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-msplLJXk-1637250894601)(https://www.zhihu.com/equation?tex=V_0)] 来说，到顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G4vGHtfc-1637250894602)(https://www.zhihu.com/equation?tex=V_1)] 的权值最小，将顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iQSwkPMO-1637250894603)(https://www.zhihu.com/equation?tex=V_1)] 加入到生成树中：

继续分析与顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FpmDfn6m-1637250894605)(https://www.zhihu.com/equation?tex=V_0)] 和 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6503hs0Q-1637250894606)(https://www.zhihu.com/equation?tex=V_1)] 相邻的所有顶点（包括 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7DmsxCmU-1637250894607)(https://www.zhihu.com/equation?tex=V_2)] 、[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EZBQiZTR-1637250894608)(https://www.zhihu.com/equation?tex=V_5)]、[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iQC1fW6A-1637250894610)(https://www.zhihu.com/equation?tex=V_6)]、[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5QTKQPdD-1637250894611)(https://www.zhihu.com/equation?tex=V_8)] ），其中权值最小的为 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PSO9tGdK-1637250894613)(https://www.zhihu.com/equation?tex=V_5)] ， 将 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TQYK3Mjr-1637250894614)(https://www.zhihu.com/equation?tex=V_5)] 添加到生成树当中：

继续分析与顶点 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zMQL1ZqY-1637250894616)(https://www.zhihu.com/equation?tex=V_0)] 和 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IN6ee59T-1637250894617)(https://www.zhihu.com/equation?tex=V_1)] 、[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sH5PJBKb-1637250894618)(https://www.zhihu.com/equation?tex=V_5)] 相邻的所有顶点中权值最小的顶点，发现为 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-33jPLsix-1637250894619)(https://www.zhihu.com/equation?tex=V_8)] ，则添加到生成树当中。

继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现为 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FJmrMXkF-1637250894621)(https://www.zhihu.com/equation?tex=V_2)] ，则添加到生成树中：

重复上面的过程，直到生成树中包含图中的所有顶点，我们直接看接下来的添加过程：

此时算法结束，我们找出了图中的最小生成树。

讲的真好!!!

搬运的视频，可以关注下这个，讲数据结构讲的真的好!

Prim算法执行过程。

Prim算法代码实现

// Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
 int min, i, j, k;
 int adjvex[MAXVEX];  // 保存相关顶点下标
 int lowcost[MAXVEX]; // 保存相关顶点间边的权值
 lowcost[0] = 0;   // V0作为最小生成树的根开始遍历，权值为0(0,3,*,*,*,4,*,*,*)
 adjvex[0] = 0;   // V0第一个加入
 // 初始化操作
 for( i=1; i < G.numVertexes; i++ )
 {
  lowcost[i] = G.arc[0][i]; // 将邻接矩阵第0行所有权值先加入数组
  adjvex[i] = 0;    // 初始化全部先为V0的下标
 }
 // 真正构造最小生成树的过程
 for( i=1; i < G.numVertexes; i++ )
 {
  min = INFINITY;  // 初始化最小权值为65535等不可能数值
  j = 1;
  k = 0;
  // 遍历全部顶点
  while( j < G.numVertexes )
  {
   // 找出lowcost数组已存储的最小权值
   if( lowcost[j]!=0 && lowcost[j] < min )
   {
    min = lowcost[j];
    k = j;  // 将发现的最小权值的下标存入k，以待使用。
   }
   j++;
  }
  //K的取值依次为：1,5,8,2,6,7,4,3
  // 打印当前顶点边中权值最小的边
  printf("(%d,%d)", adjvex[k], k);(0,1)
  lowcost[k] = 0;  // 将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历(0,0,*,*,*,4,*,*,*)
  // 邻接矩阵k行逐个遍历全部顶点(k=1,)
  for( j=1; j < G.numVertexes; j++ )
  {
   if( lowcost[j]!=0 && G.arc[k][j] < lowcost[j] )
   {
    lowcost[j] = G.arc[k][j];
    adjvex[j] = k; 
   }
  }
 }
}

时间复杂度分析

上面的代码中，当 i == 1的时候，内层的 while 与 for 循环中 j 的取值范围是从 1 到 n-1，内循环一共计算了 2(n-1) 次，其中n为图中的顶点个数；

当 i == 2 的时候，内层循环还是一共计算 2(n-1) 次；

以此类推…

i 取最大值 n -1，内层循环还是一共计算 2(n-1) 次；

所以，整体的执行次数就是 (n-1) * 2(n-1)，Prim算法的复杂度是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8fWO7UYu-1637250894629)(https://www.zhihu.com/equation?tex=O%28n%5E2%29)] 级别的。

7.5.5应用实例

某公司规模不断扩大，在全国各地设立了多个分公司，为了提高公司的工作效率，使各分公司之间的信息可以更快、更准确的进行交流，该公司决定要在各分公司之间架设网络，由于地理位置和距离等其他因素，使各个分公司之间架设网线的费用不同，公司想各分公司之间架设网线的费用降到最低，那么应该怎样来设计各分公司及总公司之间的线路？该公司的所有分公司及总公司的所在位置如下图所示，顶点代表位置及公司名称，边表示可以架设网线的路线，边上的数字代表架设该网线所需要的各种花费的总和。这样就构成了一个带权的连通图，从而问题就转化为求所得到的带权连通图的最小生成树。

这其实就是给你个连通图，让你找最小生成树嘛，上面学的那两个算法都可以实现，进行微调即可，C语言还不是太熟悉，以后更新Java的再写代码~

对比两个算法，克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高，所以对于稀疏图有很大的优势;而普里姆算法对于稠密图，即边数非常多的情况会更好一些

7.6最短路径

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点

7.6.1迪杰斯特拉( Dijkstra )算法

Dijkstra是用来求单源最短路径的

就拿上图来说，假如直到的路径和长度已知，那么可以使用dijkstra算法计算南京到图中所有节点的最短距离。

单源什么意思？

从一个顶点出发，Dijkstra算法只能求一个顶点到其他点的最短距离而不能任意两点。

摘自：

最短路径算法-迪杰斯特拉(Dijkstra)算法 - 知乎 (zhihu.com)

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想)，直到扩展到终点为止。

基本思想

通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。

此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。

初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。

然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。

重复第4步操作，直到遍历完所有顶点。

迪杰斯特拉(Dijkstra)算法图解

我在叠一层，哈哈哈

以上图为例，来对迪杰斯特拉进行算法演示(以顶点D为起点)。

看图很清晰了！

7.6.2弗洛伊德( Floyd)算法

Floyd主要计算多源最短路径。

算法的具体思想为：

邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.

从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。

而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。

重复上述直到最后插点试探完成。

默认的最短长度初始为邻接矩阵初始状态

加入第一个节点1,大家可以发现，由于1的加入，使得本来不连通的2，3点对和2，4点对变得联通，并且加入1后距离为当前最小。(可以很直观加入5之后2，4，更短但是还没加入)。为了更好的描述其实此时的直接联通点多了两条。(2,3)和(2,4).我们在dp中不管这个结果是通过前面那些步骤来的，但是在这个状态，这两点的最短距离就算它！

核心代码

public class floyd {
    static int max = 66666;// 别Intege.max 两个相加越界为负
    public static void main(String[] args) {
        int dist[][] = {
                { 0, 2, 3, 6, max, max }, 
                { 2, 0, max, max,4, 6 }, 
                { 3, max, 0, 2, max, max },
                { 6, max, 2, 0, 1, 3 }, 
                { max, 4, max, 1, 0, max }, 
                { max, 6, max, 3, max, 0 } };// 地图
        // 6个
        for (int k = 0; k < 6; k++)// 加入滴k个节点
        {
            for (int i = 0; i < 6; i++)// 松弛I行
            {
                for (int j = 0; j < 6; j++)// 松弛i列
                {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        // 输出
        for (int i = 0; i < 6; i++) {
            System.out.print("节点"+(i+1)+" 的最短路径");
            for (int j = 0; j < 6; j++) {
                System.out.print(dist[i][j]+" ");
            }
            System.out.println();
        }
    }
}

7.7拓扑排序

在一个表示工程的有向图中，有顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。

AOV网中的弧表示活动之间存在的某种制约关系。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1, V2,Vn,满足若从顶点vi到v)有一条路径，则在顶点序列中顶点Vi 必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列

7.7.2拓扑排序算法

对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

代码不妨了，以后更新Java的

一个AOV网的拓扑序列不是唯一的

检测AOV网中是否存在环方法

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

7.8关键路径

把工程计划表示为边表示活动的网络，即AOE网，用顶点

表示事件，弧表示活动，弧的权表示活动持续时间。

AOE网中没用入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点

v0，v1,…,v9分别表示事件，<v0,v1>,<v0,v2>,…<v8,v9>表示一个活动，用a0，a1…a12表示，它们的值代表活动持续时间

比如弧<V,V1>就是从源点开始的第一个活动a0，它的时间是3个单位。

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大

**长度的路径叫关键路径，在关键路径上的活动叫关键活动。**显然就图7-9-3的AOE网而言，开始→发动机完成→部件集中到位→组装完成就是关键路径，路径长度为5.5

7.8.1 关键路径算法

我们将AOE网转化为邻接表结构，注意与拓扑排序时

邻接表结构不同的地方在于，这里弧链表增加weight域，用来存储弧的权值。

关键路径算法和拓扑排序算法大概一致

小总结

图是计算机科学中非常常用的一类数据结构，有许许多多的计算问题都是用图来定义的。由于图也是最复杂的数据结构，对它讲解时，涉及到数组、链表、栈、队

列、树等之前学的几乎所有数据结构。因此从某种角度来说，学好了图，基本就等于理解了数据结构这门课的精神。

图的存储结构

邻接矩阵

邻接表

边集数组

十字链表

邻接多重表

图的遍历分为深度和广度两种，各有优缺点，就像人在追求卓越时，是着重深度还是看重广度，总是很难说得清楚。

图的应用是我们这一-章浓墨重彩的一 部分， 一共谈了三种应用:最小生成树、最短路径和有向无环图的应用。

最小生成树，我们讲了两种算法:普里姆(Prim) 算法和克鲁斯卡尔(Kruskal)算法。普里姆算法像是走一步看一步的思维方式，逐步生成最小生成树。而克鲁斯卡

尔算法则更有全局意识，直接从图中最短权值的边入手，找寻最后的答案。

最短路径的现实应用非常多，我们也介绍了两种算法。迪杰斯特拉(Dijkstra) 算法更强调单源顶点查找路径的方式，比较符合我们正常的思路，容易理解原理，但算

法代码相对复杂。而弗洛伊德(Flbyd) 算法则完全抛开了单点的局限思维方式，巧妙地应用矩阵的变换，用最清爽的代码实现了多顶点间最短路径求解的方案，原理理解有难度，但算法编写很简洁。

有向无环图时常应用于工程规划中，对于整个工程或系统来说，我们一方面关心

的是工程能否顺利进行的问题，通过拓扑排序的方式，我们可以有效地分析出一一个有向图是否存在环，如果不存在，那它的拓扑序列是什么?另方面关心的是整个工程完成所必须的最短时间问题，利用求关键路径的算法，可以得到最短完成工程的工期以及关键的活动有哪些。