• 数据结构 | 图

    文章目录

    图的基本概念

    在这里插入图片描述

    图的定义

    在这里插入图片描述

    • 图里边的顶点个数也可以称做图的阶
    • 一个图的顶点集一定是非空集，但是一个图的边集可以是空集

    图逻辑结构的应用

    在这里插入图片描述
    在这里插入图片描述

    无向图 v.s. 有向图

    在这里插入图片描述

    简单图 v.s. 多重图

    在这里插入图片描述

    顶点的度以及入度和出度

    在这里插入图片描述

    • 对于无向图来说，每一条无向边都会分别给连接这条边的两个顶点贡献一个度，所以无向图中顶点的度数总和 = 2 * 边的数量
    • 对于有向图来说，每一条有向边都会给指向的结点贡献一个入度，给发出这条边的顶点贡献一个出度，所以有向图中所有顶点的入度之和和出度之和应该是相等的，并且数值上刚好等于弧的条数

    顶点—顶点的关系描述

    在这里插入图片描述

    连通图 v.s. 强连通图

    在这里插入图片描述

    • 如果5个顶点的图要让其是连通的话，我们最少需要4条边，例如可以让一个顶点依次和其他n-1个顶点相连
      在这里插入图片描述
    • 如果是5个顶点的图，要让这个图是非连通图，则我们可以让其中4个顶点两两相连，而让其中的一个顶点孤立着，此时会有C24 = 6条边，即要让此图成为非连通图最多只能有6条边，再多一条就会和孤立的顶点连接上，图就变成连通图了
    • 要让一个图为非连通图只需要把其中一个顶点孤立，让其他顶点两两组合即可

    在这里插入图片描述

    • 但如果是有向图的话，我们要让其强连通可以构造一个回路，把所有顶点依次连接起来，只要绕着这个圈，每个顶点都会有到达其他顶点的路径，所以n个顶点的图要让其成为强连通图最少需要n条边
      在这里插入图片描述

    研究图的局部——子图

    在这里插入图片描述

    • 如果你的子图中包含了原图的所有顶点，那么这个子图就可以称作原图的一个生成子图（去掉某些边）
      在这里插入图片描述

    连通分量（无向图）

    在这里插入图片描述
    在这里插入图片描述

    强连通分量（有向图）

    在这里插入图片描述

    • 由于F这个顶点和ABCDE这几个顶点并不是强连通的，所以F要单独摘出来

    生成树

    • 包含原图里面的全部顶点又要让边尽可能地少也要保持连通的子图
      在这里插入图片描述

    生成森林

    在这里插入图片描述
    在这里插入图片描述

    边的权以及带权图/网

    在这里插入图片描述

    • 边上带权的图称为带权图，也称网

    带权图的应用举例

    在这里插入图片描述

    几种特殊形态的图

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    • 有向树并不是强连通图
      在这里插入图片描述

    图的存储

    在这里插入图片描述

    邻接矩阵法

    邻接矩阵法存储无向图

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    邻接矩阵法存储带权图（网）

    在这里插入图片描述

    • 有的时候我们也会把自己指向自己的这条边的权值设为0
    • 所以有时候在带权图当中如果有一个元素它的值是0或者∞的话，这两种状态都是表示与之对应的两个顶点不存在边
      在这里插入图片描述
    邻接矩阵法的性能分析

    在这里插入图片描述

    邻接矩阵法的性质
    • 相关证明请查阅离散数学图论相关的内容
      在这里插入图片描述
      在这里插入图片描述
    • A3 矩阵 A[0][3] = 1，背后表示的含义为A → D长度为3的路径有1条
    • 1·0 + 0·1 + 1·1 + 0·0 = 1，即从A到A长度为2的路径有1条，从A到D长度为1的路径有0条；从A到B长度为2的路径有0条，从B到D长度为1的路径有1条；从A到C长度为2的路径有1条，从C到D长度为1的路径有1条；从A到D长度为2的路径有0条，从D到D长度为1的路径有0条，两段一拼接就可以得到符合条件的一个路径
      在这里插入图片描述

    邻接表法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    十字链表

    • 十字链表法只能用于存储有向图
      在这里插入图片描述
    邻接矩阵和邻接表存储有向图

    在这里插入图片描述

    • 邻接矩阵最主要的问题是空间复杂度太高，而邻接表最主要的问题是当其存储有向图的时候要找某个顶点的入边，也就是指向一个顶点的边，十分不方便，需要遍历整个邻接表才可以
    • 十字链表法可以解决上述两个问题
    十字链表存储有向图

    在这里插入图片描述

    十字链表法性能分析

    在这里插入图片描述

    邻接多重表

    • 邻接多重表只能用于存储无向图
      在这里插入图片描述
    邻接矩阵和邻接表存储无向图

    在这里插入图片描述

    邻接多重表存储无向图

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    图的基本操作

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    图的遍历

    在这里插入图片描述

    广度优先遍历BFS

    在这里插入图片描述

    与树的广度优先遍历之间的联系

    在这里插入图片描述

    • 从根节点1出发，找到和根节点相邻的所有结点234

    在这里插入图片描述

    • 接下来从234这几个结点出发，找到与它们相邻的其他结点也就是5678这几个结点
      在这里插入图片描述
    图的广度优先遍历
    • 我们从2号结点出发开始进行广度优先遍历，最先访问的是2号结点
      在这里插入图片描述
    • 通过2号结点又可以找到下一层的1和6这两个结点，所以接下来要访问的是1和6
      在这里插入图片描述
    • 再往后，应该从1和6出发，再找到与它们相邻近的其他结点，也就是537这几个结点，因此接下来访问的就应该是537
      在这里插入图片描述
    • 最后应该再从537这几个结点出发，再找到更下一层的结点，也就是48这两个结点，因此最后访问的是48

    在这里插入图片描述

    树 vs 图

    在这里插入图片描述

    代码实现

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    • 如果我们从2号顶点出发要广度优先遍历整个图的话，首先我们要visit(2)访问2号结点并且把visited[2] = true把2号结点标记为已访问，接着让2号结点入队，队头指针指向2号结点
      在这里插入图片描述

    • 接下来就是一个while循环，如果队头元素不空的话我们就让队头元素2号结点出队，接下来我们要通过2号顶点找到与之相邻的所有的顶点，需要两个基本操作FirstNeighbor()和NextNeighbor()在for循环遍历与之相邻的所有顶点，也就是1和6
      在这里插入图片描述

    • 1和6的visited值都是false表示两个顶点之前都没有被访问过，所以这两个顶点都会被正常的visit，并且会把对应的visited数组的值设为true，对于我们访问过的顶点我们还需要把它们放到队列的队尾中
      在这里插入图片描述

    • for循环处理完了和2相邻的所有顶点，接下来就应该再进行下一次while循环，由于此时队列非空，需要让队头元素出队，也就是让1号顶点出队
      在这里插入图片描述

    • 然后又到了for循环来处理1号结点的相邻结点，和1号相邻的有2号和5号这两个结点，但是由于2号结点的visited值为true，也就意味着2号结点已经被访问过了，不满足我们if的条件，所以2号结点不会进行其他的处理
      在这里插入图片描述

    • 而对于5号结点，由于其visited值为false，所以if条件满足，因此会visit访问5号节点，并且把它相应的visited值设为true，同时把5号结点放到队列的队尾
      在这里插入图片描述

    • 接下来应该处理的应该就是6号顶点，6号顶点出队，和6号顶点相邻的是2、3、7这几个顶点，由于2号顶点已经被访问过了，所以我们只会访问3号和7号顶点，并把3号和7号顶点放到队尾
      在这里插入图片描述

    • 接下来要处理的是5号顶点，5号顶点出队，由于与5号顶点相邻的只有1号顶点并且1号顶点已经被处理过了，所以在5号顶点的for循环里面什么也不会做
      在这里插入图片描述

    • 接下来应该就是3号顶点出队，和3号相邻的有4、6、7这几个顶点，并且只有4号顶点是没有被访问过的
      在这里插入图片描述

    • 所以接下来访问4号顶点，把它的visited值设为true，同时把4号顶点放到队尾
      在这里插入图片描述

    • 接下来是7号顶点，7号顶点的for循环会检查与之相邻的所有顶点，也就是3、4、6、8这几个顶点，但是只有8号顶点是没有被访问过的，所以指挥访问8号顶点并且把8号顶点放到队尾
      在这里插入图片描述

    • 接下来队列只剩下4号顶点和8号顶点，由于和它们相邻的所有的这些顶点都已经处理完了，所有的visited值都为true，所以4、8这两个顶点的for循环里面什么也不会处理，直接出队即可

    • 这样我们就完成了对整个图G的广度优先遍历

    广度优先遍历序列

    在这里插入图片描述

    遍历序列的可变性

    在这里插入图片描述

    算法存在的问题
    • 对于非连通图，则之前的算法无法遍历完所有的结点
      在这里插入图片描述
    • 代码优化思路：我们定义的visited数组记录的是所有的顶点是否已经被访问这样的一个信息，那我们在第一次调用了BFS这个函数之后其实可以检查一下在这个visited数组中能不能找到值仍然为false的顶点，能的话就再对这些值为fasle的顶点再调用一次BFS函数即可
    BFS算法（最终Final版）

    在这里插入图片描述

    bool visited[MAX_VERTEX_NUM]; //访问标记数组

void BFSTraverse(Graph G){ //对图G进行广度优先遍历
  for(int i = 1;i < G.vexnum;i++){
    visited[i] = false; //访问标记数组初始化
  }
  InitQuene(Q); //辅助队列初始化
  for(int i = 1;i < G.vexnum;i++){ //从1号顶点开始遍历
    if(!visited[i]){ //调用一次BFS后仍有false的顶点，则表明图是非连通图，需要继续进行BFS
      BFS(G,i); //i所对应的v为访问过，从vi开始BFS
    }
  }
}

void BFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G
  visit(v);  //访问初始顶点v
  visited[v] =  true; //对v做已访问标记
  EnQuene(Q,v); //顶点v入队列Q
  while(!isEmpty(Q)){
    DeQuene(Q,v); //顶点v出队列
    for(w = FirstNeighbor(G,v);w >= 0;v = NextNeighbor(G,v,w)){ //检测v所有邻接点
      if(visited[w] == false){ //w为v尚未访问的邻接顶点
        visit(w); //访问顶点w
        visited[w]  = true;  //对w做已访问标记
        EnQuene(Q,w);  //顶点w入队列
      }
    }
  }
}

//DFS

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    复杂度分析
    空间复杂度

    在这里插入图片描述

    时间复杂度
    • 我们需要visit每一个顶点，同时在for循环里面我们还需要探索所有的这些边，所以我们可以简化地认为这个算法的时间开销主要就是来自于访问各个顶点还有探索各条边
      在这里插入图片描述
    • 对于无向图来说，无向图的邻接表这些边结点的个数应该是2|E|这么多，所以要访问一个无向图的邻接表当中所有的边结点的话，那总共需要的时间消耗应该是O(2|E|)这么多，但是大O表示法我们可以舍弃常数的系数，只保留一个O(|E|)
    广度优先生成树
    • 根据广度优先遍历的过程得来的
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 但是一个图如果是用邻接矩阵来存储的话，那么它的广度优先生成树肯定是唯一的
    广度优先生成森林

    在这里插入图片描述

    有向图的BFS过程

    在这里插入图片描述

    • 对于有向图，从不同的顶点出发进行广度优先遍历，可能会有不同的广度优先遍历趟数，如果从1号顶点出发，显然从1出发只能找到5，因此需要调用多次的BFS函数；但是如果从7号或者8号出发调用BFS的话，由于从这两个顶点出发可以找得到到其他任何一个顶点的路径，因此只需要一次BFS就可以一次性完成对所有顶点的遍历
      在这里插入图片描述

    深度优先遍历DFS

    在这里插入图片描述

    与树的深度优先遍历之间的联系
    • 树的深度优先遍历分为先根遍历和后根遍历，而图的深度优先遍历类似于树的先根遍历
      在这里插入图片描述
    • 首先要visit访问的是1号结点
      在这里插入图片描述
    • 2是1的子树，所以接下来要访问的是2号结点
      在这里插入图片描述
    • 5又是2的一个子树，所以接下来访问5号结点
      在这里插入图片描述
    • 5号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到2号结点
      在这里插入图片描述
    • 2号结点还有一个没有访问的子树，也就是6号结点，所以接下来访问6号结点
      在这里插入图片描述
    • 6号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到2号结点
      在这里插入图片描述
      在这里插入图片描述
    • 2号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到1号结点
      在这里插入图片描述
    • 1号结点还有一个子树是3号，所以接下来访问的是3号结点
      在这里插入图片描述
    • 3号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到1号结点
      在这里插入图片描述
      在这里插入图片描述
    • 1号结点还有一个没有被访问的子树，也就是4号结点，所以接下来访问的是4号结点
      在这里插入图片描述
    • 4号结点还有一个没有被访问的子树，也就是7号结点，所以接下来访问的是7号结点
      在这里插入图片描述
      在这里插入图片描述
    • 7号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到4号结点
      在这里插入图片描述
    • 4号结点还有一个没有被访问的子树，也就是8号结点，所以接下来访问的是8号结点
      在这里插入图片描述
      在这里插入图片描述
    • 8号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到4号结点
      在这里插入图片描述
    • 4号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，回到1号结点
      在这里插入图片描述
    • 1号结点的下面已经没有子树了，所以会跳出这一层的PreOrder函数递归，本次树的先根遍历执行完毕
      在这里插入图片描述
    图的深度优先遍历

    在这里插入图片描述

    • 刚开始我们进行DFS函数的时候传入的v的值是2，也就是从2号顶点开始遍历，我们首先会访问2号结点，接下来会把2号结点的visited值设置为true
      在这里插入图片描述
      在这里插入图片描述

    • for循环做的事情是要检查2号结点相邻的其他节点，和2相邻的是1、6这两个顶点，但是先来后到，和2相邻的第一个顶点应该是1号，而1号顶点此时没有被访问过，因此下一层的DFS函数我们传入的参数应该是1，那么在1号顶点这层的DFS函数中我们会访问1号顶点，并把1号顶点的visited值设为true
      在这里插入图片描述
      在这里插入图片描述

    • 接下来要检查和1号顶点相邻的其他顶点，第一个相邻的顶点是2号，但是此时2号顶点已经被访问过了，visited值为true，if条件不满足，因此2号顶点会被跳过，接下来找到的下一个和1号顶点相邻的就是5号顶点，所以下层的DFS函数传入的参数就应该是5
      在这里插入图片描述
      在这里插入图片描述

    • 访问完5号顶点后，由于和5号顶点相邻的所有顶点都已经被访问过了，所以5号顶点的这一层for循环什么也不会做，这个顶点的DFS函数执行完之后，就会返回上一层的递归调用，也就是1号顶点这一层
      在这里插入图片描述
      在这里插入图片描述

    • 由于5号顶点已经是1号顶点最后的一个邻接点，所以1号顶点的这一层for循环什么也不会做，这个顶点的DFS函数执行完之后，就会返回上一层的递归调用，也就是2号顶点这一层
      在这里插入图片描述
      在这里插入图片描述

    • 接下来通过2号顶点的for循环的基本操作会找到2号顶点的第二个邻接点，也就是6号顶点，而6号顶点此时没有被访问过，因此接下来会对6号顶点执行DFS这个函数
      在这里插入图片描述
      在这里插入图片描述

    • 在访问完6号顶点之后，又需要通过for循环找到和6号顶点相邻的其他顶点，也就是3号顶点，接下来对3号执行DFS函数
      在这里插入图片描述
      在这里插入图片描述

    • 在访问完3号顶点之后，又需要通过for循环找到和3号顶点相邻的其他顶点，也就是4号顶点，接下来对4号执行DFS函数
      在这里插入图片描述
      在这里插入图片描述

    • 在访问完4号顶点之后，又需要通过for循环找到和4号顶点相邻的其他顶点，也就是7号顶点，接下来对7号执行DFS函数
      在这里插入图片描述
      在这里插入图片描述

    • 在访问完7号顶点之后，又需要通过for循环找到和7号顶点相邻的其他顶点，也就是8号顶点，接下来对8号执行DFS函数
      在这里插入图片描述
      在这里插入图片描述

    • 在8号顶点的这一层DFS当中，由于与之相邻的所有顶点都已经被处理过了，它们的visited值都为true，因此8号顶点的DFS可以执行结束，返回上一层
      在这里插入图片描述

    • 在7号顶点的这一层DFS当中，由于与之相邻的所有顶点都已经被处理过了，它们的visited值都为true，因此7号顶点的DFS可以执行结束，返回上一层
      在这里插入图片描述

    • 在4号顶点的这一层DFS当中，由于与之相邻的所有顶点都已经被处理过了，它们的visited值都为true，因此4号顶点的DFS可以执行结束，返回上一层

    • 在3号顶点的这一层DFS当中，由于与之相邻的所有顶点都已经被处理过了，它们的visited值都为true，因此3号顶点的DFS可以执行结束，返回上一层

    • 在6号顶点的这一层DFS当中，由于与之相邻的所有顶点都已经被处理过了，它们的visited值都为true，因此6号顶点的DFS可以执行结束，返回上一层

    • 在2号顶点的这一层DFS当中，由于与之相邻的所有顶点都已经被处理过了，它们的visited值都为true，因此2号顶点的DFS可以执行结束，对这个图的深度优先遍历结束
      在这里插入图片描述

    算法存在的问题
    • 对于非连通图，则之前的算法无法遍历完所有的结点
      在这里插入图片描述
    • 代码优化思路：我们定义的visited数组记录的是所有的顶点是否已经被访问这样的一个信息，那我们在第一次调用了DFS这个函数之后其实可以检查一下在这个visited数组中能不能找到值仍然为false的顶点，能的话就再对这些值为fasle的顶点再调用一次DFS函数即可
    DFS算法（最终Final版）

    在这里插入图片描述

    //DFS
bool visited[MAX_VERTEX_NUM]; //访问标记数组

void DFSTraverse(Graph G){ //对图进行深度优先遍历
  for(int i = 1;i <= G.vexnum;i++){
    visited[i] = false; //已访问标记数组初始化
  }
  for(int v = 1;v <= G.vexnum;v++){ //本代码中是从v=1开始遍历
    if(!visited[v]){
      DFS(G,v);
    }
  }
}

void DFS(Graph G,int v){ //从顶点v出发，深度优先遍历图G
  visit(v); //访问顶点v
  visited[v] = true; //设置已访问标记
  for(int w = FirstNeighbor(G,v);w >= 0;w = NextNeighbor(G,v,w)){
    if(!visited[w]){ //w为u中尚未访问的邻接顶点
      DFS(G,w);
    }
  }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    复杂度分析
    空间复杂度

    在这里插入图片描述

    时间复杂度
    • 我们需要visit每一个顶点，同时在for循环里面我们还需要探索所有的这些边，所以我们可以简化地认为这个算法的时间开销主要就是来自于访问各个顶点还有探索各条边
      在这里插入图片描述
    • 对于无向图来说，无向图的邻接表这些边结点的个数应该是2|E|这么多，所以要访问一个无向图的邻接表当中所有的边结点的话，那总共需要的时间消耗应该是O(2|E|)这么多，但是大O表示法我们可以舍弃常数的系数，只保留一个O(|E|)
    深度优先遍历序列

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    深度优先生成树

    在这里插入图片描述
    在这里插入图片描述

    深度优先生成森林

    在这里插入图片描述

    在这里插入图片描述

    图的遍历与图的连通性

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    最小生成树

    在这里插入图片描述

    生成树

    在这里插入图片描述

    广度优先生成树

    在这里插入图片描述

    深度优先生成树

    在这里插入图片描述

    最小生成树（最小代价树）

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    求最小生成树

    在这里插入图片描述

    Prim算法（普里姆）

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    Kruskal算法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    Prim算法 v.s. Kruskal算法

    在这里插入图片描述

    Prim算法的实现思想

    在这里插入图片描述
    在这里插入图片描述

    • 更新各个顶点的lowCost值的时候只需要查看新加入的顶点和其他未加入生成树的顶点是否有比当前lowCast更少的边，有则更新
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    Kruskal算法的实现思想

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    最短路径问题

    在这里插入图片描述

    BFS算法

    BFS求无权图的单源最短路径

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    代码实现

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    • 广度优先生成树的每个节点所在的层数直接反映了从起点根节点到达这些结点的距离到底是多少
    • 最短路径也反映了以根节点为顶点构造一个广度优先生成树，这个高度肯定是最小的

    Dijkstra算法

    Absolutely 大佬

    在这里插入图片描述

    BFS算法的局限性

    在这里插入图片描述

    • 比如通过BFS算法我们得出G港到R城最短的路径是10；但是实际上G港到R城的最短路径是G港到P城再到R城5+2=7

    在这里插入图片描述

    Dijkstra算法

    在这里插入图片描述

    • 我们这里研究的例子是一个有向图，其实无向图也是一样的道理，无向图的一条无向边其实对应着有向图的两条有向边，我们只要解决了有向图，无向图的原理也是类似的
      在这里插入图片描述
    • 假设现在是要找到v0到其他各个顶点的最短路径，我们需要初始化3个数组：final数组——标记各个顶点是否已经找到最短路径；dist数组——记录目前已经找到的最短路径的长度；path数组——标明路径上的前驱
      在这里插入图片描述
    • 第一轮我们循环遍历所有的结点，找到当前还没确定最短路径，final值为false且dist值最小的顶点，令final值为true，表示的是我们现在已经可以确定对于4这个顶点它的最短路径长度就是5这么多，并且它的直接前驱是0号顶点，也就是v0
      在这里插入图片描述
    • 接下来还要做这样一件事，我们要检查所有和v4相连的顶点，也就是v1、v2、v3这几个顶点，检查一下对于这几个顶点来说如果从v4过来的话有没有可能比之前的路径还要短，有的话修改对应信息，可以看到此时v1、v2、v3的对应信息是需要修改的
      在这里插入图片描述
    • 第二轮的处理和第一轮也是一样的，我们同样需要遍历和这个顶点相关的这几个数组的信息，此时还没有找到最短路径的顶点当中目前能够找的的最小的dist值是7，也就是v3，所以接下来我们要处理的是v3这个顶点，把对应的final值设为true，表示我已经确定到达v3的最短路径总长度为7，并且是从4号顶点过来的
      在这里插入图片描述
    • 接下来我们要检查所有的能从v3过去的顶点，只需要检查final值为false的那些点，如果从v3过来的话有没有可能比之前的路径还要短，有的话修改对应信息，可以看到此时v2的对应信息是需要修改的

    在这里插入图片描述

    • 第三轮的处理和第一、二轮也是一样的，我们同样需要遍历和这个顶点相关的这几个数组的信息，此时还没有找到最短路径的顶点当中目前能够找的的最小的dist值是8，也就是v1，所以接下来我们要处理的是v1这个顶点，把对应的final值设为true，表示我已经确定到达v1的最短路径总长度为8，并且是从4号顶点过来的
      在这里插入图片描述

    • 接下来我们要检查所有的能从v1过去的顶点，只需要检查final值为false的那些点，如果从v1过来的话有没有可能比之前的路径还要短，有的话修改对应信息，可以看到此时v2的对应信息是需要修改的
      在这里插入图片描述

    • 第四轮的处理和第一、二、三轮也是一样的，我们同样需要遍历和这个顶点相关的这几个数组的信息，此时还没有找到最短路径的顶点当中只剩下v2了，所以接下来我们要处理的是v2这个顶点，把对应的final值设为true，表示我已经确定到达v2的最短路径总长度为9，并且是从1号顶点过来的

    • 此时已经找不到final值为false的其他顶点，所以我们就不需要做其他的操作了，迪杰斯特拉算法到此结束
      在这里插入图片描述

    如何使用数组的信息？

    在这里插入图片描述

    Dijkstra算法时间复杂度

    在这里插入图片描述

    • 如果用计算机实现迪杰斯特拉算法，应该怎么做呢？
    • 假设各个顶点的编号是从0开始，并且我们要找的是v0这个顶点到其他顶点的最短路径，在初始的时候只有v0的final值要设为true，其他的都是false，同时v0的dist值为0，path值为-1，表示v0之前没有前驱结点，v0就是起点，而对于其他的顶点，也需要进行设置
      在这里插入图片描述
    • arcs[0][k]表示的是从起始顶点v0到其他顶点的弧的长度，如果不存在弧的话长度就是无穷
    • 那么对于没有和起点直接相连的那些顶点我们需要把它们的path值设为-1，和起点v0直接相连的那些顶点我们需要把它们的path值设为0
    • 初始化结束之后接下来需要进行n-1轮处理，每一轮的处理都会导致我们能够确定一个新顶点的最短路径
      在这里插入图片描述
    Dijkstra算法用于负权值带权图可能会失效

    在这里插入图片描述
    在这里插入图片描述

    Floyd算法

    Absolutely 大佬

    在这里插入图片描述

    Floyd算法

    在这里插入图片描述

    • 动态规划思想：将一个大问题的求解分为多个阶段，每个阶段之间又有一个递进的关系

    • 刚开始我们不允许各个顶点之间的路径存在其他的中转顶点，所有的顶点之间都不允许有中转点
      在这里插入图片描述

    • 接下来我们要考虑各个顶点之间如果允许v0顶点进行中转的话，最短路径有没有可能得到进一步的缩短，我们需要通过上一阶段的矩阵的信息求得下一阶段的最优矩阵A0和path0
      在这里插入图片描述
      在这里插入图片描述

    • 接下来我们要考虑各个顶点之间如果允许v0、v1顶点进行中转的话，最短路径有没有可能得到进一步的缩短，我们需要通过上一阶段通过v0中转的矩阵的信息再加上v1中转求得下一阶段的最优矩阵A1和path1
      在这里插入图片描述
      在这里插入图片描述

    • 接下来我们要考虑各个顶点之间如果允许v0、v1、v2顶点进行中转的话，最短路径有没有可能得到进一步的缩短，我们需要通过上一阶段通过v0、v1中转的矩阵的信息再加上v2中转求得下一阶段的最优矩阵A2和path2
      在这里插入图片描述

    在这里插入图片描述

    矩阵A和path矩阵的用法

    在这里插入图片描述

    Floyd算法核心代码

    在这里插入图片描述

    Floyd算法实例

    在这里插入图片描述

    • 有了初始状态之后接下来我们考虑在v0这个点作为中转，也就是当k=0的时候，把A矩阵当中的所有的元素进行一次检查，然后进行值的更新，但此时我们发现所有的值都不需要更新，矩阵的状态不发生改变
    • 在图中更好理解，在图中没有任何一条边能到得了v0，所以我们允许从v0中转也无济于事
      在这里插入图片描述
    • 接下来我们需要增加考虑如果以v1顶点作为中转，当k=1的时候，把A矩阵当中的所有的元素进行一次检查，然后进行值的更新
      在这里插入图片描述
      在这里插入图片描述
    • 接下来我们需要增加考虑如果以v2顶点作为中转，当k=2的时候，把A矩阵当中的所有的元素进行一次检查，然后进行值的更新
      在这里插入图片描述
    • 这里有A[2][3]，但是在图中我们发现2号顶点和3号顶点其实是没有直接相连的边的，所以在这个地方，我们能很好地体会到这个算法其实已经考虑到了以v1作为中转顶点的情况，现在这一步的计算是基于之前的最优结果来增加v2作为中转顶点的
    • 这里的A[0][3]其实是v0-v2-v1-v3，整个路径当中其实已经考虑到了可以以v2、v1、v0这些顶点作为中转的情况
      在这里插入图片描述
    • 接下来我们需要增加考虑如果以v3顶点作为中转，当k=3的时候，把A矩阵当中的所有的元素进行一次检查，然后进行值的更新
      在这里插入图片描述
      在这里插入图片描述
    • 接下来我们需要增加考虑如果以v4顶点作为中转，当k=4的时候，把A矩阵当中的所有的元素进行一次检查，然后进行值的更新
      在这里插入图片描述
    • 以上就是我们得到的最终的两个矩阵的值
    • 接下来我们看一下怎么用这两个矩阵来找最短路径
    • 比如现在我们要找v0到v4的最短路径，从A矩阵可以看到它们之间的最短路径的长度是4，但是这个最短路径的完整信息找起来会比上面3个顶点的例子要麻烦
    • v0到v4，中间需要有一个中转点v3，也就是说v0需要先到v3，然后v3再到v4，但是在图中，v0到v3并没有一条直接存在的路径，所以其实v0到v3的最短路径是需要我们迭代地往里面填充一些中转顶点的
    • v0到v3的最短路径，在矩阵中可以看到，其实还需要经过v2，所以v0到v3的最短路径我们中间还需要添加v2，v3到v4的最短路径中间是没有中转点的，所以这两个结点之间我们不需要再加任何结点，v0到v2的最短路径中间是没有中转点的，所以这两个结点之间我们不需要再加任何结点，v2到v3的最短路径，在矩阵中可以看到，其实还需要经过v1，所以v2到v3的最短路径我们中间还需要添加v1
    • 这样我们就得到了完整的最短路径信息
      在这里插入图片描述
      在这里插入图片描述
    Floyd算法用于负权图

    在这里插入图片描述

    Floyd算法不能解决带有负权回路的图

    在这里插入图片描述
    在这里插入图片描述

    有向无环图描述表达式

    有向无环图DAG

    在这里插入图片描述

    DAG描述表达式

    在这里插入图片描述

    • 我们的算术表达式可以用树来表示，这个表达式中存在着一些重复的部分，在树中表示为红色和绿色的这两棵子树，从计算的角度来看这两个子树的计算结果是一样的，会导致重复计算，我们可以只保留一份，节省存储空间

    在这里插入图片描述

    • 上面的结构其实就是一个有向无环图DAG，不难发现上面其实还有可以合并的地方
      在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    • 规律：顶点之中是不可能出现重复的操作数的
      在这里插入图片描述

    解题方法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    • 按顺序加入运算符的时候注意“分层”，也就是如果一个运算需要基于下面一层的运算的结果来进行的，就需要把这个运算符放在上面一层的位置
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 由于操作数是不重复地排列，所以我们只需要检查操作符有没有需要合并的，我们需要自底向上逐层检查同层的运算符是否可以合体
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 到此为止，我们就得到了一个最简的，用有向无环图来表示的算数表达式
      在这里插入图片描述
    • 为什么我们在自底向上逐层检查运算符是否可以合体的时候只需要检查【同一层】的运算符就可以呢？
    • 可以这么理解，最底层的运算符，它的左右操作数是直接对某一个具体的数来进行的，而上面一层的运算，左边或者右边中的某一个操作数或者是两者，肯定是一个复合的操作数表达式，所以上面出现的运算符和底下的一层运算符肯定是不可能合并的，所以我们只需要一层一层地往上检查就可以了

    练习

    在这里插入图片描述

    • 首先把各个操作数不重复地排成一排
      在这里插入图片描述

    • 标出各个运算符的生效顺序（先后顺序有点出入无所谓）
      在这里插入图片描述

    • 按顺序加入运算符，注意“分层”
      在这里插入图片描述

    • 从底向上逐层检查同层的运算符是都可以合体
      在这里插入图片描述
      在这里插入图片描述

    • 如果改变运算符的生效次序，会发现我们的有向无环图的层数会低一层
      在这里插入图片描述
      在这里插入图片描述

    • 如果我们用有向无环图来存储一个表达式，那么这个图最终形态是不唯一的
      在这里插入图片描述

    拓扑排序

    • 拓扑排序也是有向无环图DAG的一个应用

    AOV网

    • Activity On Vertex NetWork，用顶点表示活动的网
      在这里插入图片描述
    • 顶点表示活动，有向边表示活动先后的进行顺序
      在这里插入图片描述
    • AOV网一定是个有向无环图，如果图里面存在环路则不能构成AOV网
      在这里插入图片描述
    • 切番茄的时候需要先洗番茄，洗番茄之前又需要切番茄，阿噢~死锁了

    拓扑排序

    在这里插入图片描述

    • 拓扑排序：找到做事的先后顺序
      在这里插入图片描述
    • 要做番茄炒蛋这个大工程，一开始我们可以选择两个事件作为起点，我们可以先准备厨具或者先买菜
      在这里插入图片描述
    • 我们选择先【准备厨具】
      在这里插入图片描述
    • 现在工具有了，我们需要【买菜】，因为后面的工序需要鸡蛋和番茄，没买菜之前是不能得到这些食材的
      在这里插入图片描述
    • 现在番茄和鸡蛋都有了，我们可以选择先打鸡蛋或者先洗番茄，这里我们选择先【洗番茄】
      在这里插入图片描述
    • 再往后我们可以选择先切好番茄或者先打鸡蛋，我们选择先【切番茄】
      在这里插入图片描述
    • 先在把番茄准备好了，我们需要打鸡蛋，因为没有鸡蛋我们肯定没办法下锅炒，所以接下来做的事情是【打鸡蛋】

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    • 入度为0表示当前顶点在它之前不需要有任何的准备活动，所以我们需要把入度为0的这些顶点先输出
    • 输出定点之后我们需要把该顶点和所有以它为起点的有向边都删除
    • 接下来不断重复，直到AOV网为空或者当前网中不存在无前驱的顶点为止
      在这里插入图片描述
    • 只要一个图中存在着回路，那么这个图一定不能被拓扑排序
      在这里插入图片描述

    拓扑排序的代码实现

    在这里插入图片描述
    在这里插入图片描述

    • 将一开始图中所有入度为0的顶点压入栈S中
      在这里插入图片描述
    • 选择一个栈顶元素出栈，并把输出的顶点信息保存在数组中
      在这里插入图片描述
    • 遍历当前出栈的顶点，找到其指向的顶点，把所有的指向的顶点的入度减1，并将入度减为0的顶点压入栈S中
      在这里插入图片描述
    • 栈顶元素出栈，并把输出的顶点信息保存在数组中
      在这里插入图片描述
    • 遍历当前出栈的顶点，找到其指向的顶点，把所有的指向的顶点的入度减1，并将入度减为0的顶点压入栈S中
      在这里插入图片描述
    • 栈顶元素出栈，并把输出的顶点信息保存在数组中
      在这里插入图片描述
    • 遍历当前出栈的顶点，找到其指向的顶点，把所有的指向的顶点的入度减1，并将入度减为0的顶点压入栈S中
      在这里插入图片描述
    • 栈顶元素出栈，并把输出的顶点信息保存在数组中
      在这里插入图片描述
    • 遍历当前出栈的顶点，找到其指向的顶点，把所有的指向的顶点的入度减1，并将入度减为0的顶点压入栈S中
      在这里插入图片描述
    • 栈顶元素出栈，并把输出的顶点信息保存在数组中
      在这里插入图片描述
    • 此时没有其他结点了，while循环结束，并且count的值为5，等于结点的数量，所以拓扑排序成功，本次拓扑排序结束

    逆拓扑排序

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    逆拓扑排序的实现

    在这里插入图片描述

    逆拓扑排序的实现（DFS算法）

    • 不要忘了复习下如何用DFS算法实现拓扑排序
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 拓扑排序算法也经常用于判断一个图中有没有环路
      在这里插入图片描述

    关键路径

    AOE网

    • Activity On Edge NetWork，用边表示活动的网络
      在这里插入图片描述
      在这里插入图片描述

    关键路径

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    求关键路径的步骤

    在这里插入图片描述

    求所有事件的最早发生时间

    在这里插入图片描述

    • 所有指向该事件的活动都发生之后该事件才能够发生，所以用的是max
    求所有事件的最迟发生时间
    • 汇点的最迟发生时间和其最早发生时间其实是一样的
      在这里插入图片描述
    求所有活动的最早发生时间
    • 每个活动的最早发生时间就是这个活动的弧尾所连的这个事件的最早发生时间
      在这里插入图片描述
    求所有活动的最迟发生时间

    在这里插入图片描述

    • 对于所有的活动最晚发生时间其实就是这条弧所指向的这个结点的最晚发生时间减掉这条弧的权值
    求所有活动的时间余量

    在这里插入图片描述

    求得关键活动和关键路径

    在这里插入图片描述

    关键活动和关键路径的特性

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  • 相关阅读:
    RPA技术的优点，个人学习RPA有哪些好处？
    爬虫破解：解决CSRF-Token反爬问题 - 上海市发展和改革委员会
    java数据类型与变量的安全性
    Caffeine缓存的使用
    继承day01
    如何用蓝牙实现无线定位（三）--本地定位显示
    express学习7-express参数中post参数的获取
    A Philosophy of Software Design读书笔记——异常处理
    MySQL入门第六天——函数与条件查询
    vlan同步—VTP通告
  • 原文地址：https://blog.csdn.net/weixin_44043952/article/details/126328369