MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
我不知道那个算法叫什么名字。。

先说说什么是强连通分量,也就是在这个分量中,所有的点都相互可达~~

当明白什么是强连通分量的时候,就可以看一个图说出他们的强连通分量了。

算法:
    1。当深度搜索一棵树的时候,如果第一次搜索到某个强连通分量的点时,这个点我们记录为a,那么,经过一系列深度搜索后,这个连通分量里的所有的点的完成时间,即后序遍历序号,即算法导论里面说的变成“黑色”的点地时间,一定是最长的。因为深度搜索的特性决定的。   
    2。我们把一个连通分量的边变成反向的,它同样还是连通的。


应用这个,再结合算法,算法说  先正dfs原图,然后按照后序便利需要从大到小dfs原图的逆图。

其实就是根据上面2个原理。要从后序便利序号来dfs原图是抓住每个连通分量的a,这样不会漏掉连通分量,而把图倒过来以后,连通性仍然保持,再dfs就可以了。



posted on 2008-09-04 15:12 memorygarden 阅读(1128) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理