ppt课件和代码图论ex代码和课件图论ex.pdfVIP

图论ex wjh 有向图的强联通分量 无向图的双联通分量 树的直径 最近公共祖先（LCA） 名词解释 ● 强连通：有向图中，两个顶点至少存在一条路径 ● 强连通图：每两个顶点都强连通的有向图 ● 强连通分量（Strongly Connected Components）：有向图的极大强连通子图 问题模型 ● 对于一些存在依赖关系的模型，若其建图是一 DAG，则可以直接通过拓扑排序解 决，但若其中有环则需要特殊处理 ● 对于有环的问题，会出现一些互相依赖的关系，这些关系组成了一个强连通分量，根 据题目要求的性质，对于这个强连通分量可以将其缩为一个点 ● 将所有强连通分量缩成点后即可在DAG上求解 ● 建模方式和DAG很相似，建出图不是DAG就先跑一边SCC缩点即可 有向图边的类型 ● 使用DFS从任意节点遍历有向图时，可以得到DFS树 ● 每一条边和DFS树的关系，可以分为以下四种 – 树枝边：DFS树上的边，即指向未 过节点的边 – 前向边：指向DFS树中子树中节点的边 – 后向边：指向DFS树中父亲的边 – 横叉边：其他边，即指向DFS树中非子树的边 ● 下面考虑如何判断这四种边 判定方式 ● 红色标记为DFS树 ● 记录dfs序 ● A边终点未 过，为树枝边 ● B边终点已被 过，且 dfn[v]dfn[u]，说明在子树中，说 明为前向边 ● C边终点已被 过且不在子树中，终 点在栈中则为后向边 ● D边终点已被 过且不在子树中且已 经出栈，为横叉边 Tarjan ● 在一个有向有环图上DFS，找出每一个强连通分量 ● 考虑每一个强连通分量高度最低（离根近）的那个点 ● 这些点将DFS树分割成了许多个子树，每个子树中的点组成了一 强连通分量 ● 分割的方法是在dfs同时另外维护一个栈存放节点，离开分割点时把 分割点往下的部分全部取出来就是一个强连通分量。 ● 现在需要找到这些分割点 low[] ● 维护一个数组low，low[u]代表点u所能到达子树中的，深度最小的点祖先的dfs序 编号 ● 初始low[u]=dfn[u] ● 对于边(u,v) – 若为树枝边，则用low[v]更新 – 若为后向边，则用dfn[v]更新 – 若为前向边，因为指向的点的 已经通过树枝边传递过来，所以无需更新 – 若为横叉边，则指向另一个强连通分量，无需更新 ● 当low[u] == dfn[u]时，就是一个分割点 模板 P3387 无向图的双连通性 ● 对于无向图，定义双连通性 – 点双连通：删去任何一个点仍然连通 – 边双连通：删去任何一条边仍然连通 ● 另一种定义是，任何两点之间至少存在两条不经过相同中间点（边）的路径 ● 如果不满足双连通性 – 割点（割顶）：删去后原图不连通的顶点集合 – 割边（桥）：删去后原图