图论

把对象与关系抽象为点和边，从存储、遍历与树的结构出发，逐步学习路径、连通性、生成树、网络流和匹配。建模时先辨明方向、权值与约束，再选择算法并检查复杂度。

61 个条目

图论基础

先掌握图的表示与遍历，再沿有向无环图、环与特殊图类展开；计数、随机游走和支配关系各有不同的建模目标。

利用树上两点间路径唯一的结构，学习直径、中心、重心与祖先查询，再用剖分、虚树和分治组织路径及子树信息。

先区分单源与多源、负权与非负权，再选择松弛和扩展方式；把不等式或余数状态转成边时，要说明路径长度对应的实际量。

从连通且无环的选边要求出发，区分总权最小、有向根可达与直径最小等目标；新增约束后，需要重新检查交换性质是否成立。

区分有向可达与无向连通，借助分量分解、割点和桥识别关键连接，再用缩点或圆方树把整体问题转成更简单的结构。

用容量与流量守恒描述资源分配，先理解残量网络、增广和割，再加入费用或流量上下界；全局最小割需与固定源汇的割区分。

把配对关系建成边，分别考虑匹配数量、边权总和与偏好稳定性；先判断是否为二分图，再选择增广或处理奇环的方法。