模板

求有向图的所有强连通分量

jxtxzzw · · ·

求有向图的强连通分量SCC(Strongly connected component)一般用的都是Tarjan算法。

这个算法的原理不赘述了。

核心的部分就是,如果u可以到达v,且v在栈中,low[u]=min{low[u],dfn[v]},如果v不在栈中,low[u]=min{low[u],low[v]}

我在实现的时候遇到了一个错误,调试了很久,现在记下来。

if (visited[v]==0) {
    tarjan(v);
    LOW[u] = min(LOW[u],LOW[v]);
} else if (inStack[v]==1) {
    LOW[u] = min(LOW[u], DFN[v]);
}

如果v没有被访问过,tarjan搜索(类似于DFSv

这里要特别特别注意:

如果v没有被访问过,那么他一定不会在栈中,所以uLOW等于uvLOW较小的一个。

如果v被访问过,那么要分两种情况:

如果v还在栈中,那么说明刚才只是深搜到的v入栈了,那么就uLOW就是LOW[u]DFN[v]中较小的一个。

如果v不在栈中了,这里不可以再做LOW[u]=min(LOW[u],LOW[v]),所谓的“如果点v不在栈中,那么LOW[u]=min{LOW[u],LOW[v]}”,前提是v根本不属于任何强连通分量,如果v被访问过,且不在栈中,那么仅有一种可能——当且仅当v被输出过。这是因为v在栈中,要么没有被访问过,要么已经被输出了,但是现在已知v被访问过了,那么v就是属于别的连通分量,被输出了。所以这里的visited[v]==1 && inStack[v]==0是什么都不能做的,我一开始做了一个更新LOW,那就出事了。

小结一下:

visited==0 && inStack==0 : 没有被访问过,递归tarjan,并且更新LOW[u]=min(LOW[u],LOW[v])

visited==0 && inStack==1 : 不可能存在的情况

visited==1 && inStack==0 : 已经处理过这个点了,在其他的强连通分量输出过了,什么都不用做

visited==1 && inStack==1 : 更新LOW[u]=min(LOW[u],DFN[v])

附Tarjan算法核心代码:

/**
 * 求强连通分量SCC,找到就输出
 * @param u 当前检查的顶点编号
 */
void tarjan(int u) {
    DFN[u] = LOW[u] = ++times;
    visited[u] = inStack[u] = 1;
    stack[top++] = u;
    L_NODE* p = head[u];
    while (p!=NULL) {
        int v = p->ver;
        if (visited[v]==0) {
            tarjan(v);
            LOW[u] = min(LOW[u],LOW[v]);
        } else if (inStack[v]==1) {
            LOW[u] = min(LOW[u], DFN[v]);
        }
        p = p->link;
    }
    if (DFN[u] == LOW[u]) {
        printf("Strongly Connected Component %d: ", ++scc);
        int v;
        do {
            v = stack[--top]; 
            printf("%d ",v);
            inStack[v]=0;
        } while (u!=v);
        printf("\n------\n");
    }
}

0 条回应