本文写于 2018年01月01日,距今已超过 1 年,距 2020年07月25日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

求有向图的强连通分量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 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论