图论的小技巧和易错点

Part 0 题目在解题前需要先明确题目的图的模型边题目中的边代表什么给定的是点权还是边权如果是点权应该如何转为边权边是有向边还是无向边图图是简单图吗是否存在重边或自环存在重边或自环时应该如何处理或者它是一棵树规模题目是否给出了顶点数n nn和边数m mm还是需要手工计算n nn和m mmPart 1 建图Part 1.1 邻接表为什么要使用邻接表存图而不是其他方式存入的是代表是否两点连通的01还是边权Part 1.2 邻接矩阵作者不常用所以没有总结出太多的易错点和技巧……Part 1.3 链式前向星边是否无向如果是存边的数组大小是否达到了2 × N 2 \times N2×N边的编号是从0 00开始还是1 112 22开始注意边双连通分量的建图必须从2 22开始。Part 2 最短路FloydFloyd 算法一般使用「邻接矩阵」进行存图。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​未被正确计算或未计算导致结果错误。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小心出题人卡 SPFASPFA 在某些特殊构造的数据下可能退化为O ( N × M ) O(N \times M)O(N×M)的时间复杂度。Dijkstra适用条件用于无负权边的图。使用前应明确求的是单源最短路还是多源最短路每个点的初值是否足够大源头节点的初值是0 00或是x xx边权的含义。版本朴素版本适用于稠密图。堆优化版本适用于大多数图。过程更新边权的时候可以直接更新吗还是像旅行巴士一样有一些限制。Part 3 其他其他内容敬请期待…