引入
Kosaraju 算法用于求解强连通分量,在稠密图下复杂度会比 tarjan 算法要优秀。(?
过程
-
对整个图进行搜索,并且将没一个顶点按照 DFS 序压入栈中。
-
建一个反图。
-
对于栈中的每一个点再反图上跑一遍 DFS,现在跑出来的子图即为一个强连通分量。
-
标记这几个点。
-
重复执行操作3,4,直到栈为空。
code
复杂度
其最坏情况就是每个点和每一条边都需要进行两次 DFS,这样子的复杂度为 \(O(N + E)\)。\(N\) 为点数,\(E\) 为边数。但是一般都是跑不满的。
在稠密图上表现良好,个人认为这个算法会比 tarjan 好写许多。
标签:tarjan,复杂度,算法,DFS,Kosaraju,反图 From: https://www.cnblogs.com/Carousel/p/18171709