最小生成树

最小生成树性质

  • 最小生成树不是惟一的，当图中的各边权值互不相等时，最小生成树唯一；若无相连接图边比顶点树少1，本身就是 一个数，最小生成树是他本身。
  • 最小生成树的边的权值总司惟一的
  • 最小生成树的边数为定点数减1

prim算法；普利姆算法

  1. 从图中找到第一个起顶点V0，作为生成树的第一个顶点，然后从这个顶点到其他顶点所有边中选择权值最小的边，然后把这条边的哦另一个顶点V和这条边加入生成树。
  2. 对剩下的其他的所有顶点，分别检查这些顶点与v的权值是都比这些顶点在lowcost数组中对应的权值小，如果更小，则用最小的权值更新lowcost数组。
  3. 从更新后的lowcost数组中继续挑选权值最小而且不在生成树的边，然后加入生成树中。
  4. 反复执行2和3直到所有的顶点都加入到生成树中
  5. 算法时间复杂度分析为

克鲁斯卡尔算法(kruskal)

  • 将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。
  • 克鲁斯卡尔算法操作分为对边的权值排序部分和一个单重for循环，它们是并列关系，由于排序耗费时间大于单重循环，所以克鲁斯卡尔算法的主要时间耗费在排序上。排序和图中边的数量有关系，所以适合稀疏图。
  • 时间复杂度

最短路径

迪杰斯特拉（dijkstra算法）

  1. 初始化：集合S初始为{0}，dist[]的初始值dist[i]=arcs[0][i]，i=1，2，…，n-1。
  2. 找出dist[]中的最小值dist[j]，将顶点j加入集合S，即修改s[vj]=1。
  3. 修改从v0出发到集合V-S上任一顶点vk可达的最短路径长度：如果dist[j] + arcs[j][k]< dist[k]，则令dist[k]=dist[j] + arcs[j][k]。另外更新path[k]=j(也就是顶点j加入集合之后如果有新的路径使得到顶点k路径变短的话就将到顶点k的路径长度修改成较短的)
  4. 重复2）～3）操作共n-1次，直到所有的顶点都包含在S中。
  5. 算法时间复杂度分析为

弗洛伊德

  • 求出每个顶点的最短路径

  • 算法思想： 递推产生一个n阶方阵序列 其中表示从顶点vi到顶点vj的路径长度，k表示绕行第k个顶点的运算步骤。初始时，对于任意两个顶点vi和vj，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以∞作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k(k=0，1，…，n-1)作为中间顶点。如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径

  • 算法时间复杂度分析为

拓扑排序

  • 如果我们把每个环节看成图中一个顶点，在这样一个有向图中，用顶点表示活动，用弧表示活动之间的优先关系，那么这样的有向图称为AOV网(Activity On Vertex) 由于弧是用来表示活动之间的优先关系，或者说AOV网具有实际的意义，那么AOV网显然是不能有回路的 有向无环图也叫做DAG图
  • 拓扑排序算法： 从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的顶点为止。

关键路径

  • 源点：入度为零
  • 汇点：出度为零
  • 关键路径：从源点到汇点路径长度最长的路径
  • 可能不止一条关键路径
  • 四个描述
  1. ve（vj）-表示vj的最早发生时间
  2. vl(vj)-表示vj的最迟发生时间
  3. e（i）表示活动的最早开始时间
  4. l（i）表示活动ai最迟开始时间
  5. 时间余量：l（i）-e（i）
  6. 关键活动：l（i）-e（i）=0，关键活动

** ve（vj）正着算，求最大值，vl(vj)逆着算，求最小值，**

如上图