【数据结构】图论算法笔记整理

图的遍历

  • 有两种存储方式:邻接矩阵和邻接表
  • 在一些顶点数目比较大(一般顶点个数在1000以上)的情况下,使用邻接表而不是邻接矩阵来存储图。如果是稀疏图,用邻接表,如果是稠密图,用邻接矩阵。

深度优先搜索dfs遍历图

  • 按深度优先的方式访问所有未被访问的结点,在结点被访问过后标记为已访问

广度优先搜索bfs遍历图

  • 建立一个队列,把初始定点加入队列,然后每次都取出队首元素进行访问,并把该定点除法可以到达的未曾加入过队列(而不是未访问)的定点全部加入队列,直到队列为空

最短路径

  • 单源最短路径:计算源点到其他各顶点的最短路径的长度
  • 全局最短路径:图中任意两点的最短路径
  • Dijkstra、Bellman-Ford、SPFA求单源最短路径
  • Floyed可以求全局最短路径,但是效率比较低
  • SPFA算法是Bellman-Ford算法的队列优化
  • Dijkstra算法不能求带负权边的最短路径,而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
  • Bellman-Ford算法的核心代码只有4行,Floyd-Warshall算法的核心代码只有5行。
  • 深度优先遍历可以求一个点到另一个点的最短路径的长度

Dijkstra算法

  • 三种附加考法:第一标尺是距离,如果距离相等的时候,新增第二标尺
    • 新增边权(第二标尺),要求在最短路径有多条时要求路径上的花费之和最小

    • 给定每个点的点权(第二标尺),要求在最短路径上有多条时要求路径上的点权之和最大

    • 直接问有多少条最短路径

    增加一个数组num[],num[s] = 1,其余num[u] = 0,表示从起点s到达顶点u的最短路径的条数为num[u]

  • 例子:比如说又要路径最短,又要点权权值最大,而且还要输出个数,而且还要输出路径

  • of course, 可以不用这么麻烦,用Dijkstra求最短路径和pre数组,然后用深度优先遍历来获取想知道的一切,包括点权最大,边权最大,路径个数,路径
  • 因为可能有多条路径,所以Dijkstra部分的pre数组使用vector<int> pre[maxv];
  • 既然已经求得pre数组,就知道了所有的最短路径,然后要做的就是用dfs遍历所有最短路径,找出一条使第二标尺最优的路径
  • 解释:
    • 对于递归边界而言,如果当前访问的结点是叶子结点(就是路径的开始结点),那么说明到达了递归边界,把v压入temppath,temppath里面就保存了一条完整的路径。如果计算得到的当前的value大于最大值,就path = temppath,然后把temppath的最后一个结点弹出,return ;
    • 对于递归式而言,每一次都是把当前访问的结点压入,然后找他的pre[v][i],进行递归,递归完毕后弹出最后一个结点
  • 计算当前temppath边权或者点权之和的代码:
  • 计算路径直接在Dijkstra部分写就可以
  • 例子:计算最短距离的路径和最小花费
  • 关于初始化:除了weight和cost(点权和边权)都要初始化,pre初始化为它自己本身,e和dis初始化为inf,visit因为开了全局变量,自动初始化为了false。在dijkstra循环开始之前,要把dis[start] = 0;

【最短路径】之Dijkstra算法

最短路径

  • 单源最短路径:计算源点到其他各顶点的最短路径的长度
  • 全局最短路径:图中任意两点的最短路径
  • Dijkstra、Bellman-Ford、SPFA求单源最短路径
  • Floyed可以求全局最短路径,但是效率比较低
  • SPFA算法是Bellman-Ford算法的队列优化
  • Dijkstra算法不能求带负权边的最短路径,而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
  • Bellman-Ford算法的核心代码只有4行,Floyd-Warshall算法的核心代码只有5行。
  • 深度优先遍历可以求一个点到另一个点的最短路径的长度

Dijkstra算法

  • 三种附加考法:第一标尺是距离,如果距离相等的时候,新增第二标尺
    • 新增边权(第二标尺),要求在最短路径有多条时要求路径上的花费之和最小

    • 给定每个点的点权(第二标尺),要求在最短路径上有多条时要求路径上的点权之和最大

    • 直接问有多少条最短路径

    增加一个数组num[],num[s] = 1,其余num[u] = 0,表示从起点s到达顶点u的最短路径的条数为num[u]

  • 例子:比如说又要路径最短,又要点权权值最大,而且还要输出个数,而且还要输出路径

  • of course, 可以不用这么麻烦,用Dijkstra求最短路径和pre数组,然后用深度优先遍历来获取想知道的一切,包括点权最大,边权最大,路径个数,路径
  • 因为可能有多条路径,所以Dijkstra部分的pre数组使用vecto<int> pre[maxv];
  • 既然已经求得pre数组,就知道了所有的最短路径,然后要做的就是用dfs遍历所有最短路径,找出一条使第二标尺最优的路径
  • 解释:
    • 对于递归边界而言,如果当前访问的结点是叶子结点(就是路径的开始结点),那么说明到达了递归边界,把v压入temppath,temppath里面就保存了一条完整的路径。如果计算得到的当前的value大于最大值,就path = temppath,然后把temppath的最后一个结点弹出,return ;
    • 对于递归式而言,每一次都是把当前访问的结点压入,然后找他的pre[v][i],进行递归,递归完毕后弹出最后一个结点
  • 计算当前temppath边权或者点权之和的代码:
  • 计算路径直接在Dijkstra部分写就可以
  • 例子:计算最短距离的路径和最小花费

【最短路径】:Dijkstra算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法

求最短路径最常用的算法有:
Dijkstra算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法。
Dijkstra算法、SPFA算法、Bellman-Ford算法这三个求单源最短路径,最后一个Floyd-Warshall算法可以求全局最短路径也可以求单源路径,效率比较低。
SPFA算法是Bellman算法的队列优化
Dijkstra算法不能求带负权边的最短路径,而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行,Floyd-Warshall算法的核心代码只有5行。

1.最基本的求单源最短路径方法是图的深度优先遍历
用 min = 99999999 记录路径的最小值,book[i]标记结点 i 是否被访问过~

2.单源最短路径:Dijkstra算法
dis[i]是需要不断更新的数组,它表示当前结点1(源点)到其余各结点的最短路径长度~
book[i]标记当前结点最短路径是确定值还是估计值~
算法实现的过程是:每次找到离结点1最近的那个点,然后以该结点为中心扩展,最终得到源点到所有点的最短路径~~每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质~~
找到所有估计值当中最小的值min以及它的结点u,然后把该结点u标记为确定值,通过这个确定值为中转点更新别的所有值的最短路径(松弛别的两个顶点连接的边)

3.Bellman-Ford算法——解决负权边
算法思想:对所有的边进行n-1次“松弛”操作

4.Bellman-Ford的队列优化(SPFA算法)
每次选取首顶点u,对u的所有出边进行松弛操作~如果有一条u->v的边,通过这条边使得源点到顶点v的路程变短,且顶点v不在当前队列中,就把这个顶点v放入队尾。同一个顶点在队列中出现多次是毫无意义的,所以用一个数组来判重复,判断哪些点已经在队列中。对顶点u的所有出边都松弛完毕后,就将顶点v出队~