最短路

01BFS

只有两种边权时, 使用01BFS寻找最短路,可以做到$O(E+V)$

改用双端队列维护,0放队首,1放队尾

经典例子就是4方向的障碍网格图

Floyd

定义状态 $f[k][i][j]$ 表示只能经过节点 $1$ 到 $k$ 时从 $i$ 到 $j$ 的最短路

此时有转移方程:

$$f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])$$

注意到 $f[k][i][j]$ 只与 $f[k-1][i][j]$ 和 $f[k-1][i][k]+f[k-1][k][j]$ 相关, 所以可以滚动数组优化

这样三重循环即可

Dijkstra

单源最短路, 不能有负边

将节点分为两类, 已确定最短路的节点s1和未确定最短路的节点s2

每次取出s2中距离最短的点放入s1, 然后松弛该点的出边

连通分量

一般用于缩点, 当忽略某些信息的时候, 将图转为一颗树, 从而更好的使用一些树的性质与算法

强连通分量

如果两个点相互可达,则它们在同一个SCC中

用于缩点, 可以很好的简化图 -> 转为DAG

可以使用Tarjan做到一次DFS找到所有SCC:

• 维护两个数组, dfs时间戳和节点能访问的最早时间戳
• 那显然, 如果一个点的最早时间戳和dfs时间戳相同, 那么它就是一个SCC的根节点
• 这样DFS即可找到所有SCC

经典问题: 你有一个图，其中每个节点代表一个多米诺骨牌。如果从某个节点（多米诺骨牌）开始推，它会推动该节点的所有邻居（即该节点指向的所有节点）。你需要找到最少的节点数量，分别对它们进行推倒操作，使得所有节点都会被触发（即所有的多米诺骨牌都会倒下）。

双连通分量

定义: 在无向图上, 没有割点/桥的连通分量

点双具备传递性, 这是很好的性质

同样用于缩点, 点双可以用于将图转换为圆方树

类似的做Tarjan,

• 边双,当low[v]>dfn[u]时,弹出栈中边
• 点双,当low[v]>=dfn[u]时,弹出栈中边(root特判)

并查集

维护一个集合的划分关系, 支持合并与查询

使用路径压缩+按秩合并优化时, 时间复杂度$O(\alpha (n))$

普通并查集

维护一个fa表示根节点即可

直接给代码更直观一些(这里就不写按秩合并了,都是一样的,额外维护rnk即可):

查询

int find(int x) {
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

合并

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        fa[x] = y;
    }
}

带权并查集

引入weight表示对于root的距离, 可以很好的维护更多的关系

比如维护一个维护模3意义下的加法群, 可以替代扩展域并查集解决「NOI2001」食物链这题

拓扑排序

用于对DAG节点排序,不具备唯一性

每次取入度为0的点,然后更新它的出边,然后如此bfs即可

最小生成树

无向图中边权和最小的生成树,不具备唯一性

Kruskal

按边权排序, 然后每次取最小的边, 如果它的两个端点不在一个集合, 就合并它们, 否则忽略它(并查集维护即可)

时间复杂度$O(E\log E)$

Prim

逐步增加节点, 每次选择当前节点的出边中最小的边, 加入生成树中, 并更新生成树的节点

时间复杂度$O((E+V)\log V)$

环问题

最大环

拓扑排序暴力找即可

最坏情况下退化为哈密顿回路，属于NP-hard问题

最小环

对每个点跑一次BFS

带权最小环

对每个边跑一边迪杰斯特拉

最小环即为删除这条边跑的最短路+边长