求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.doc

求强连通分量的Kosaraju算法和Tarjan算法的比较 一定义 在有向图中如果两个顶点vi,vj间有一条从vi到vj的有向路径同时还有一条从vj到vi的有向路径则称两个顶点强连通(strongly connected)如果有向图的每两个顶点都强连通则称该有向图是一个强连通图非强连通的有向图的极大强连通子图称为强连通分量(strongly connected components) 而对于一个无