时间戳

首页 > 技术文章 > 图论连通性及算法

图论连通性及算法

lingfunny 2022-06-04 18:07 原文

图论连通性及算法

强连通分量

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

tarjan 算法求强连通分量

举个栗图：

首先，从任意一个节点（这里假设为 1）开始进行 dfs，可以得到一棵 dfs 树。

我们记 dfn[u]​ 为节点 \(u\)​​​​ 的 dfs 序，low[u] 为这棵 dfs 树子树 u 中的所有节点通过一条非树边可以到达的最小的 dfs 序。下图为这张图的 dfs 树，其中紫色为非树边，蓝色为节点的 dfn：

TARJAN_SEARCH(int u)
    vis[u]=true
    low[u]=dfn[u]=++dfncnt
    push u to the stack
    for each (u,v) then do
        if v hasn't been search then
            TARJAN_SEARCH(v) // 搜索
            low[u]=min(low[u],low[v]) // 回溯
        else if v has been in the stack then
            low[u]=min(low[u],dfn[v])

上面即 tarjan 算法过程。

我们可以发现，对于一个连通分量图，在该连通图中有且仅有一个节点 \(u\)​，其 dfn[u]=low[u]。而栈中 \(u\) 及其后面的结点构成一个 SCC。

int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 scc 的编号
int sz[N];       // 强连通 i 的大小
void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

tarjan 的两个数组 dfn 与 low 还有其它性质：

对于节点 \(u\)​​​​​​​​ 的所有儿子 \(v\)​​​​​，均有 low[v] >= dfn[u] 时，\(u\)​​​​​ 为割点。

对于一条边 \((u,v)\)，若 low[v] > dfn[u]，这条边为割边。

Kosaraju 算法

Kosaraju 算法也是一个求强连通分量的算法，同时更加简便，依靠两次简单的 DFS 实现。

第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。

第二次 DFS，对于原图的反向图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。

// g 是原图，g2 是反图

void dfs1(int u) {
  vis[u] = true;
  for (int v : g[u])
    if (!vis[v]) dfs1(v);
  s.push_back(u);
}

void dfs2(int u) {
  color[u] = sccCnt;
  for (int v : g2[u])
    if (!color[v]) dfs2(v);
}

void kosaraju() {
  sccCnt = 0;
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs1(i);
  for (int i = n; i >= 1; --i)
    if (!color[s[i]]) {
      ++sccCnt;
      dfs2(s[i]);
    }
}

双连通分量

下文大部分照抄 OI-wiki。

在一张连通的无向图中，对于两个点 \(u\) 和 \(v\)，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 和 边双连通 。

在一张连通的无向图中，对于两个点 \(u\)​ 和 \(v\)​，如果无论删去哪个点（只能删去一个）都不能使它们不连通，我们就说 和 点双连通 。

边双连通具有传递性，即若 \(x,y\)​​ 边双连通，\(y,z\) 边双连通，则 \(x,z\) 边双连通。

点双连通不具有传递性，反例如下图，\(A,B\)​ 点双连通，\(B,C\)​ 点双连通，而 \(A,C\)​ 不点双连通。

DFS 找桥并判断边双连通

首先，对原图进行 DFS。

bcc-1.svg

如上图所示，黑色与绿色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边 覆盖 了这条树上路径上所有的边。绿色的树边 至少 被一条非树边覆盖，黑色的树边不被 任何 非树边覆盖。

我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。

如何统计一条边是否被覆盖了呢？考虑差分。对于一条非树边 \((u,v)\)​​​，在 depth 小的节点 \(v\)​​​ 上打上 \(+1\)​​​ 的标记，而在 \(u\)​​​ 打上 \(-1\)​​​ 的标记。这样对于每个节点，若其子树和为正数，则其连向父亲的边必不为桥，子树和为 \(0\)​​​ 则反之。

这样，对于两个点 \((u,v)\)，两点双连通当且仅当这两点间路径不含桥。

void dfs(int u, int fa) {
    vis[u] = true;
    for(int i=hd[u];i;i=e[i].nxt) {
        edge& e = E[i];
        if(e.v == fa) continue;
        if(vis[e.v]) {
            ++cnt[u];
            --cnt[v];
        }
        else dfs(e.v, u);
    }
}

DFS 找割点并判断点双连通

如上图所示，黑色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径。

考虑一张新图，新图中的每一个点对应原图中的每一条树边（在上图中用蓝色点表示）。对于原图中的每一条非树边，将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块（这在上图中也用蓝色的边体现出来了）。

这样，一个点不是割点，当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块。两个点点双连通，当且仅当它们在原图的树上路径中的所有边在新图中对应的蓝点都属于同一个连通块（即两点之间的路径没有割点）。

推荐阅读