图论

图论（Graph Theory） 是数学的一个分支，研究图的性质和应用。图（Graph） 由若干顶点及连接两顶点的边构成，用于描述事物之间的关系。顶点代表事物，边表示事物间的关联。

章节目录

基础概念

专题	说明
图论相关概念	图的基本定义和术语
图的存储	邻接矩阵、邻接表、链式前向星
DFS	图上的深度优先搜索
BFS	图上的广度优先搜索

树上问题

专题	说明
[[01.树基础	树基础]]
[[02.树的直径	树的直径]]
[[04.树的重心	树的重心]]
[[05.最近公共祖先	LCA]]
[[06.树链剖分	树链剖分]]
[[09.树分治	树分治]]

图的遍历与排序

专题	说明
DAG	有向无环图及其性质
拓扑排序	DAG的线性排序

最短路问题

专题	算法	时间复杂度
最短路	综述	-
-	Dijkstra	$O ((n + m) lo g m)$
-	Bellman-Ford	$O (nm)$
-	Floyd	$O (n^{3})$
-	Johnson	$O (nm lo g m)$

生成树问题

专题	说明
最小生成树	Kruskal、Prim算法
[[最小树形图	最小树形图]]
斯坦纳树	连接指定点集的最小树

连通性

专题	说明
割点和桥	图的关键点和边
双连通分量	点/边双连通分量
强连通分量	Tarjan、Kosaraju算法
2-SAT	布尔可满足性问题

特殊图

专题	说明
欧拉图	一笔画问题
哈密顿图	经过所有顶点的回路
二分图	可二着色的图
平面图	可平面嵌入的图
弦图	无诱导长环的图

网络流

专题	说明
[[22.网络流	网络流]]
最大流	Ford-Fulkerson、Dinic
最小割	最大流最小割定理
费用流	最小费用最大流

图匹配

专题	说明
图匹配	匹配问题概述
二分图匹配	匈牙利算法
二分图最大权匹配	KM算法

其他

专题	说明
拆点	将点拆成入点和出点
环计数	图中环的计数
最小环	图中最小环
图着色	点着色、边着色

参考资料

此文件夹下有29条笔记。