强连通分量【k 算法、t 算法】

2022-10-22,,

连通分量就是一个各个顶点能互相达到的图

无向图的连通分量选取任意一个顶点使用DFS遍历即可,遍历完所有顶点所需的DFS的次数就是连通分量的数量

有向图的强连通分量由于是有向的【从A点开始DFS能访问到B点,但不一定能从B返回A】,所以不能简单地认为遍历完顶点就行,这时只有选取正确的顶点顺序进行DFS才能得到正确的结果。有篇博客写得很好,安利一波:https://www.cnblogs.com/nullzx/p/6437926.html

算法:通过取反图,然后DFS后序遍历【就是先遍历未被访问顶点的所有未被访问的顶点,再遍历该点】将点放入栈中,从栈顶【最后一个入栈的】开始取就是一个符合上述要求的正确的顺序。

t 算法:时间复杂度优于 k 算法。主要通过两个数组记录1)instack[i]顶点是否在递归栈中,2)vis[i]顶点是否被遍历。【如果不在栈中并且被访问了,直接返回,不能使用那个点进行更新栈内点的low[u]值,因为就不是一个栈内的也就是不是一个环上的,而如果在栈中并且被访问了,说明有环,就能回溯更新环上点u的low[u]值】继续安利博客:【博主懒...】https://blog.csdn.net/qq_16234613/article/details/77431043

强连通分量【k 算法、t 算法】的相关教程结束。

《强连通分量【k 算法、t 算法】.doc》

下载本文的Word格式文档,以方便收藏与打印。