有向图的强连通分量(SCC)
对于一个有向图,有点u到点v可达,不一定意味着v到u可达,对于一个有向图,如果任意两点间都相互可达,则该图称为一个强连通图。若任意两点间要么u可达v,要么v可达u则称该图为单侧连通图。若去掉有向图的方向后为一个连通图则为弱连通图。对于一个图,若其不是强连通图,但是总可以找到它的连通分量,使得联通分量的点都是相互可达的,对于极大的连通分量即为图的强连通分量(Strongly Connected Component, SCC),类似的有图的单侧连通分量,和弱连通分量。求一个图的弱连通分量,只需要用dfs或者bfs对图做一下遍历即可,有几棵树就有几个弱连通分量。对于求单侧连通分量,????。对于求有向图的强连通分量有以下算法:
1. 对有向图以某个节点做dfs记录各点的结束时间。
2. 将图所有边反向,以结束时间从大到小,再做一遍dfs,如果从某个点可以遍历到一些点,则这些点可以构成一个强连通分量。
SCC求强连通分量的伪代码(邻接表表示,且同时完成了缩点操作,缩点时一般还需要对一些量进行特殊设定,需要在缩点时进行修改,该题是缩点时记录新节点包括旧图中的几个节点。)
posted on 2010-07-12 18:51 YUANZX 阅读(709) 评论(0) 编辑 收藏 引用
Powered by: C++博客 Copyright © YUANZX