标签:图论
25 个条目
-
概念 欧拉图
经过每条边恰好一次的图结构;无向图由奇度顶点个数判定,有向图还需入度与出度平衡且弱连通。
2026-11-20 -
概念 欧拉图判定
线性判断无向图或有向图是否存在欧拉回路或欧拉迹:无向图看奇度顶点与连通性,有向图看入度出度平衡与弱连通。
2026-11-20 -
概念 哈密顿图
经过每个顶点恰好一次的图结构;含哈密顿回路的图称为哈密顿图,一般图判定是 NP 完全的,Dirac 与 Ore 条件给出充分判定。
2026-11-20 -
用栈不断走未使用的边,回溯时把顶点追加到答案,反转后得到欧拉迹;时间与 n+m 成正比。
2026-11-20 -
概念 二分图
顶点可分成两侧、所有边都跨两侧的无向图;等价于无奇环,可用二染色判定。
2026-11-17 -
概念 二分图判定
判断无向图是否二分图,并在是时给出二染色;BFS/DFS 染色,冲突等价于奇环。
2026-11-17 -
概念 二分图匹配
二分图中两两不共端点的边集;最大匹配与完美匹配可由最大流或两个划分拟阵的交刻画。
2026-11-17 -
概念 Borůvka 算法
每一轮让每个连通块选出一条最小出边并同时合并,O(log n) 轮得到最小生成树。
2026-11-15 -
概念 Kruskal 算法
把边按权值排序,用并查集依次加入不成环的边,最终得到最小生成树。
2026-11-15 -
概念 最小生成树
带权连通图中边权和最小的生成树;由割性质与环性质刻画,不一定唯一。
2026-11-15 -
概念 Prim 算法
从单个点出发,每次把连接已选集合的最小边加入,逐步扩展出最小生成树。
2026-11-15 -
概念 双权瓶颈路径
每条边有两个权值 (a,b),最小化路径上 max a + max b;按 a 扫描,用按 b 的 MST 回答瓶颈。
2026-11-12 -
概念 图
图由顶点和边组成;涵盖有向/无向、度、路径、连通性与子图,是树、MST 和 DAG 的基础。
2026-11-11 -
概念 生成树
连通无向图中包含全部顶点的一棵树;恰有 n-1 条边,是 MST、生成森林和树形结构的基础。
2026-11-11 -
概念 Borůvka 算法实现
Borůvka 算法的并查集实现,含调用示例和实现细节。
2026-11-10 -
概念 瓶颈生成树
以最小化最大边权为目标的生成树;任一棵 MST 都是瓶颈生成树,但反过来不一定。
2026-11-10 -
概念 Kruskal 算法实现
Kruskal 算法的并查集实现,含调用示例和实现细节。
2026-11-10 -
概念 最小生成森林
不连通带权无向图中,每个连通块各取一棵 MST 得到的最小权森林;连通时退化为 MST。
2026-11-10 -
概念 Prim 算法实现
Prim 算法的堆优化与邻接矩阵实现,含调用示例和实现细节。
2026-11-10 -
概念 树
连通无环无向图;n 个点 n-1 条边,任意两点有唯一简单路径,是有根树、DFS 序和树形 DP 的基础。
2026-11-10 -
隐式稠密图上用 Borůvka 的 O(log n) 轮,把每轮化为最优出边 oracle;具体谓词结构与 SOS DP 见实例页。
2026-11-10 -
Borůvka 隐式图模型的实例索引:主理想、Rectilinear MST、XOR-MST,以及通用的紧凑最值查询条件。
2026-11-10 -
Borůvka 隐式图模型中以主理想为核心的 oracle 实例:布尔格 Zeta 变换 / SOS DP、树形偏序子树最值、DAG 可达性的双主理想。
2026-11-10 -
概念 补图连通性
给定稀疏图,求补图的连通块;用未访问集合做 BFS,间接遍历稠密补图,O((n+m) log n)。
2026-11-10 -
题目 01-MST
完全图边权只有 0/1,给定权值为 1 的边;MST 权值为 0 边补图的连通分量数减 1。
2026-11-10