图论的小技巧和易错点

Part 0 题目

在解题前，需要先明确题目的图的模型：

1. 边：题目中的边代表什么？给定的是点权还是边权，如果是点权，应该如何转为边权？边是有向边还是无向边？
2. 图：图是简单图吗？是否存在重边或自环，存在重边或自环时应该如何处理？或者它是一棵树？
3. 规模：题目是否给出了顶点数n nn和边数m mm？还是需要手工计算n nn和m mm？

Part 1 建图

Part 1.1 邻接表

0. 为什么要使用邻接表存图，而不是其他方式？
1. 存入的是代表是否两点连通的0，1还是边权？

Part 1.2 邻接矩阵

作者不常用，所以没有总结出太多的易错点和技巧……

Part 1.3 链式前向星

1. 边是否无向，如果是，存边的数组大小是否达到了2 × N 2 \times N2×N？
2. 边的编号是从0 00开始还是1 11，2 22开始（注意边双连通分量的建图必须从2 22开始）。

Part 2 最短路

Floyd

0. Floyd 算法一般使用「邻接矩阵」进行存图。

1. Floyd 的最外层k为什么必须放在最外层？

   解释

   Floyd 算法的主要思想是动态规划，其状态转移方程为：
   d i s i , j = min ⁡ ( d i s i , j , d i s i , k + d i s k , j ) dis_{i,j} = \min(dis_{i,j},\; dis_{i,k} + dis_{k,j})disi,j​=min(disi,j​,disi,k​+disk,j​)
   （最短路场景），或在传递闭包场景中的：
   d i s i , j = d i s i , k ∧ d i s k , j dis_{i,j} = dis_{i,k} \land dis_{k,j}disi,j​=disi,k​∧disk,j​
   算法必须保证在计算d i s i , j dis_{i,j}disi,j​时，所有以1 11到k − 1 k-1k−1为中间点的最短路径（或传递关系）都已计算。

   若将k kk放入内层循环，可能在更新d i s i , j dis_{i,j}disi,j​时，所需的d i s i , k dis_{i,k}disi,k​或d i s k , j dis_{k,j}disk,j​未被正确计算或未计算，导致结果错误。

2. Floyd 算法可以计算每个节点恰好或至多经过k kk步可达的点集。
   恰好 k 步：初始可达数组d i s disdis的k kk次方
   至多 k 步：为每个节点i ii增加一条自环（即d i s i , i = 1 dis_{i,i} = 1disi,i​=1），再进行k kk次方。

SPFA

1. 小心出题人卡 SPFA，SPFA 在某些特殊构造的数据下可能退化为O ( N × M ) O(N \times M)O(N×M)的时间复杂度。

Dijkstra

适用条件

用于无负权边的图。

使用前应明确

1. 求的是单源最短路还是多源最短路？
2. 每个点的初值是否足够大？
3. 源头节点的初值是0 00或是x xx？
4. 边权的含义。

版本

朴素版本：适用于稠密图。
堆优化版本：适用于大多数图。

过程

1. 更新边权的时候可以直接更新吗，还是像旅行巴士一样有一些限制。

Part 3 其他

其他内容敬请期待…