朝花夕拾-桥与强连通分量

Posted on Edited on

[toc]

桥

  • 桥是在无向图中不在环上的边.
  • 如果隔断桥，无向图将被分为两个不连通的子图.

割点

  • 如果删去一个点, 余下的点不连通, 则这个点是割点.
  • 割点不依赖桥, 桥上也不一定存在割点.

如何找桥和割点

  1. 任选图上一点为根, dfs.
    • 记录每个节点首次被访问的次序, 记作dfn[x].
    • 记录每个节点能连接或通过子节点连接到的最早节点的dfn, 且不能沿父亲边, 记作low[x].
    • dfs(x)将返回low[x].
  2. 在每个dfs中, 设当前节点为x, 枚举边连到y.
    • 如果dfn[y]未定义, 则y是x在搜索树上的儿子. low[x] = min(low[x], dfs(y)).
    • 如果y == fa[x], 则y是x在搜索树上的父亲, 不管此y
    • 若dfn[y]有定义且y!=fa[x], 则y即是x通过非父子边连到的节点, 尝试用dfn[y]更新low[x].
  3. 利用桥和割点的性质判定.

性质/依据

沿x的边找其他节点y.

  1. dfn[y]有定义 <==> y是x在搜索树中的祖先
    • 充分性是显然的.
    • 必要性: 若y不是祖先, 则y是兄弟或祖先的兄弟. 又因为dfn[y]有定义, 所以y一定完成了dfs的过程, 但x和y连接的边却没有处理, 矛盾.
    • 尝试用dfn[y]更新low[x], 而不是用low[y]. (使回溯边不经过祖先点). 这样能保持算法的正确性. 否则因为回溯边经过割点在找割点时产生错误.
  2. 若y是x在搜索树上的非第一个儿子:
    • 若x是根, 则y与之前的儿子以x为割点.
    • 若x不是根, 则y与之前的儿子可能经过x的祖先联通.
      • 如果验证y与x的祖先不连通, 则x是两者的割点.
      • 如果验证y与x的祖先不连通, 则x是y与其他儿子的割点(否则y已经被访问过, 不会是x的儿子.)

桥的性质

  1. 桥是一条边, 连接着在搜索树中的父亲和儿子/祖先和儿子
  2. 设一条边连接着祖先节点u, 儿子节点v, 若dfn[u]<low[v], 则若边删除, 祖先儿子无法连通, 即此边是桥. 反之亦然: 边(u, v)是桥 <==> dfn[u]<low[v] (u是v的祖先)

割点的性质

  1. 割点是一个点, 它要么是根节点, 要么有一个父亲节点.
  2. 对于根节点, 若搜索树上根节点有多余一个儿子, 则任意两对儿子以根节点为割点.
  3. 对于非根节点, 设为u, 其父亲为fa, 儿子v(i), 若dfn[u] <= low[v], 则若u删除, fa/v不连通, 即u是割点; 特别地, dfn[u] <= low[v1], 则v1与v2, v3....都以fa为割点.

找桥：用dfs遍历图，记录结点访问次序；当某个结点有一条边通往已被访问过的结点时，代表找到了环；不在环上的边就是桥。

强连通分量

在有向图中两个顶点Vi，Vj之间有一条从Vi到Vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量（百度百科）

Kosaraju算法:

1、深搜遍历原图G图，记录每个结点离开时间（后序遍历）；

2、选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。

3、如果还有点没有被删除，重复2，否则算法结束

Kosaraju算法性质：如果将求出来的强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的结点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。