图论整理

文章目录

• 最短路
• 连通性
• 生成树
• 团和独立集
• 欧拉和汉密尔顿
• 流
• 树
• others

最短路

SPFA

dijkstra：已处理集合和待处理集合

floyd：DP

差分约束

最短路图，最短路树：

例题：每第一次到一个点可以ban掉一条边，求最坏情况最短路

k短路：A*

连通性

强连通

点双

边双

tarjan

支配树（dominator tree）

例题：DZY loves Chinese II，claris the final battle

生成树

矩阵树定理

基尔霍夫矩阵

斯坦纳树

K小生成树、平面图的最小生成树、最小度数生成树、度数限制生成树、最小乘积生成树、最小直径生成树

（平面图三角剖分？？）

团和独立集

极大团和最大团

最大团和最大独立集

最大团

极大团计数 BK算法

欧拉和汉密尔顿

欧拉路径算法×2

竞赛图有汉密尔顿路径

贝斯特定理

流

最小平均值环 小栗酱

树

prufer数列

长链剖分

others

计数三元环和四元环，O(mlogm)，容斥