【图论】—— 二分图_匈牙利算法 正确性-爱代码爱编程
如果一张无向图的 N 个结点 可以分成 A,B 两个非空集合，其中 ，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。A.B分别称为二分图的左部和右部。 二分图的判定 定理： 一张图是二分图，当且仅当图中不存在奇数环（长度是奇数的环）。 染色法判二分图 根据上述的定理，我们可以用染色法进行二分图判定
【图论】—— 有向图的强连通分量_玄澈_的博客-爱代码爱编程
给定有向图 ，若存在 ，满足从 出发能到达 中所有的点，则称 是一个“流图”（ Flow Graph ），记为 ，其中， 称为流图的源点。 在一个流图 上从 进行深度优先遍历，每个点只访问一次。所有发生递归的边 （换言之，从 到 是对 的第一次访问）构成一棵以 为根的树，我们把它称为流图 的搜索树。 同时，在深度优先遍历的
【图论】—— 最小生成树_玄澈_的博客-爱代码爱编程
最小生成树 给定一张边带权的无向图 , 。由 V 中全部 n 个顶点和 E 中 n - 1条边构成的 无向连通子图 被称为 G 的一棵生成树。 边的权值之和最小的生成树被称为无向图 的最小生成树 定理 任意一颗最小生成树一定包含无向图中权值最小的边 证明： 反证法。假设无向图 存在一棵最小生成树不含权值最小的边。 设
【图论】—— 最近公共祖先（lca）_玄澈_的博客-爱代码爱编程
给定一颗树，若节点 z 既是 节点 x 的祖先， 也是节点 y 的祖先，那么称 z 为 x、y 的公共祖先。 在 x、y 的所有公共祖先中，深度最大的一个称为 x、y 的最近公共祖先， 也称 LCA(x, y) LCA(x, y) 是 x 到根的路径与 y 到根的路径的交汇点。它也是 x 与 y 之间的路径上深度最小的节点。 树上倍增法
【图论】—— 差分约束系统_玄澈_的博客-爱代码爱编程
差分约束 差分约束系统是一种特殊的N元一次不等式组。它包含N个变量 ，以及 N 个约束条件， 每个约束条件都是由两个变量作差构成的，形如 ，其中 可以是常数（可以是非负数，也可以是负数）， 。 我们要解决的问题就是：求一组解 ，使得所有的约束条件都得到满足。 差分约束系统中的每个约束条件 可以变形为 。这和单源最短路问题中的三角
【图论】—— bellman-ford算法和spfa算法_玄澈_的博客-爱代码爱编程
给定一张有向图，若对于图中的某一条边 ，有 成立，则称该边满足三角形不等式。如果所有边都满足三角形不等式，则 数组就是所求的最短路。 Bellman-Ford算法 表示的是一条从 x 出发， 到达 y ，长度为 z 的有向边。 首先介绍基于迭代的Bellman-Ford算法，它的流程如下： 扫描所有边 ，若 , 则用 更新 重复上
【图论】—— spfa判负环 + 01分数规划_玄澈_的博客-爱代码爱编程
关于SPFA 【图论】—— Bellman-Ford算法和SPFA算法_玄澈_的博客-CSDN博客 负环 给定一张有向图（无向图的每条边可以看做是两条方向相反的有向边，从而按照有向图处理），每条边都有一个权值（长度）。若一条边的长度是负数，则称它是负权边。若存在一个环，环上各边的权值之和是负数，则称这个环为“负环”。