APTX Blog

A Moe Blog Set By APTX

C/C++:Tarjan算法求有向图强连通分量

文章目录[隐藏]

笔记

1、出度:以顶点v为起点的弧的数目

入度:顶点v为终点的弧的数目

2、如果在有向图G中,有一条<u,v>有向道路,则v称为u可达的,或者说,从u可达v。

3、强连通图:若有向图G的任意两个顶点都互相可达,则称图 G是强连通图,如果有向图G存在两顶点u和v使得u不能到v,或者v不能到u,则称图G是强非连通图。

4、强连通分量:如果有向图G不是强连通图,他的子图G2是强连通图,点v属于G2,任意包含v的强连通子图也是G2的子图,则称G2是有向图G的极大强连通子图,也称强连通分量。

5、极大强连通子图(强连通分量)解释:一个图的强连通子图,并且加入任何一个不在它的点集中的点都会导致它不再强连通。

6、强连通分量里边的任意两个点,都是互相可达的。

算法解析

1、Tarjan算法,是一个基于Dfs(深搜)的算法,假设我们要先从0号节点开始Dfs,我们发现一次Dfs我门能遍历整个图,而且我们发现,在Dfs的过程中,我们深搜到 了其他强连通分量中,那么我们Dfs之后如何判断哪个和那些节点属于一个强连通分量呢?

之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图,就是一个完整的搜索树。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。

2、首先引入两个数组

3、Tarjan算法在搜索过程中把没有Tarjan过的点入栈并将该节点的dfn[i] = low[i] = ++dfs_num(也就是设成他自己),然后以这个节点为树根再进行搜索,当一颗子树搜索完毕时回溯,并在回溯时比较当前节点和目标节点的LOW值,将较小的LOW值赋给当前结点的LOW,这样可以保证每个节点在以其为树根的子树的所有节点中LOW值是最小的。如果回溯时发现当前节点DFN[i]==LOW[i],就将栈中当前结点以上的节点全部弹栈,这些点就组成了一个强连通分量。还要注意一点是,当目标节点进行过Tarjan但还在栈中,就拿当前节点LOW值与目标节点DFN值比较,把更小的赋给当前结点的LOW。

①对于从没访问过的节点:加入栈中让其DFN[i]=LOW[i]=++dfs_num,让vis[i]=1表示该点入栈了。这类点的标志是!DFN[i]&&!vis[i]。

②对于访问过但不在栈中的节点(!vis[i])直接回溯即可,因为既然该节点访问过了又不在栈中,就必定属于另一个强连通分量。这类点的标志是DFN[i]&&!vis[i]。

②对于访问过且在栈中的节点,比较当前节点LOW值和目标节点DFN值,将较小的赋给当前结点LOW值然后回溯。这类点的标志是DFN[i]&&vis[i]。

算法模板

评测:洛谷:P2863

 

参考:

https://blog.csdn.net/mengxiang000000/article/details/51672725

https://blog.csdn.net/qq_34374664/article/details/77488976

https://www.cnblogs.com/reddest/p/5932153.html

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注