求强连通分量的三种算法——Kosaraju, Tarjan, Gabow

张文泰 posted @ 2010年1月18日 02:00 in Art of Science with tags 图论 强联通分量 , 11926 阅读

就我所知,有三种时间复杂度为O(n)的方法可以求强连通分量,分别是Kosaraju、Tarjan和Gabow。

  1. Kosaraju
    算法的步骤为
    • 对图G进行DFS,并按照遍历完成的先后顺序进行标号。
    • 将图G中所有的边反向得到G'。
    • 对G'进行DFS,每轮DFS都选择编号最大的点最为当前的遍历树的根。
    • 最后,遍历得到的森林就是SCC的集合。
    该算法的优点在于,最后得到的节点是按照拓扑序组织好的,在求解2-SAT的过程中十分方便。
  2. Tarjan
    第一个求解SCC的算法,应用非常广泛,几乎任何和图的遍历有关的问题都可以套用Tarjan算法的思想(比如,求割点、桥、块等等)。
    在遍历时,对每一个节点定义时间戳,同时定义Low函数,含义为节点及其子孙通过非父子边的返祖边所能到达的最小时间戳。最后若Low函数等于其时间戳,则当前递归栈内存在一个SCC。
    代码如下:
    void dfs(int index) {
      low[index] = dfn[index] = cnt++;
      used[index] = 1;
      del[index] = 0;
      st[top++] = index;
      for (int i = last[index]; i!=-1; i = e[i].nxt)
        if (!used[e[i].y]) {
          dfs(e[i].y);
          if (low[index]>low[e[i].y]) low[index] = low[e[i].y];
        }
        else if (!del[e[i].y]) if (low[index]>dfn[e[i].y])
          low[index] = dfn[e[i].y];
      if (low[index]==dfn[index]) {
        do {
          root[st[--top]] = index;
          del[st[top]] = 1;
        } while (st[top]!=index);
      }
    }
    
  3. Gabow
    算法的原理说起来太麻烦,还是直接给出代码。其实这个算法并不是很常用。
    #include <cstdio>
    #include <cstring>
    #include <stack>
    
    using namespace std;
    
    const int MAXN = 1000;
    
    struct node {
      int tar;
      node *nxt;
      node(int _tar,node *_nxt)
        : tar(_tar),nxt(_nxt) {}
    };
    
    node *g[MAXN];
    int n,m,co,all,dfn[MAXN],id[MAXN];
    stack<int> vec,path;
    
    void dfs(int x) {
      dfn[x] = co++;
      vec.push(x);
      path.push(x);
      for (node *i = g[x]; i!=NULL; i = i->nxt)
        if (dfn[i->tar]==-1) dfs(i->tar);
        else if (id[i->tar]==-1)
          while (dfn[path.top()]>dfn[i->tar]) path.pop();
      if (path.top()==x) path.pop();
      else return;
      for (int i; ;) {
        id[i = vec.top()] = all;
        vec.pop();
        if (i==x) break;
      }
      all++;
    }
    
    int main() {
      freopen("gabow.in","r",stdin);
      freopen("gabow.out","w",stdout);
      scanf("%d%d",&n,&m);
      memset(g,0,sizeof(g));
      for (int i = 0,a,b; i<m; i++) {
        scanf("%d%d",&a,&b); a--; b--;
        g[a] = new node(b,g[a]);
      }
      co = all = 0;
      memset(dfn,-1,sizeof(dfn));
      memset(id,-1,sizeof(id));
      for (int i = 0; i<n; i++)
        if (dfn[i]==-1) dfs(i);
      for (int i = 0; i<n; i++)
        printf("%d\n",id[i]);
      return 0;
    }
    

本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License
xiaodao 说:
2010年9月14日 14:51

赞,学习了。。#


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter