强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图

Presentation on theme: "强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图"— Presentation transcript:

1 强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
Kosaraju算法（双DFS) 基本图算法 强连通分量 实现算法： Tarjan算法 Gabow算法 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图 1、任意两顶点都连通称该图为强连通图 2、否则将其中的极大连通子图称为强连通分量 a b c d e f g h １２

2 强连通分量 a b d g h e f 强连通分量： {abe} ,{cd} ,{fg} ,{h} 求强连通分量过程 a b c d e f
基本图算法 强连通分量 Kosaraju算法（双DFS) a b c d a b C d 13/14 11 /16 1 /10 8 /9 g h 12 /15 3 /4 2 /7 5 /6 e f e f g h step1：对原图G进行深度优先遍历，算出每个节点的 完成时间。 step2：对原图求反。 step3：选择具有最晚离开时间的顶点进行遍历,删除能 够遍历到的顶点，这些顶点构成一强连通分量。 强连通分量： {abe} ,{cd} ,{fg} ,{h} step4：如果还有顶点没有删除，继续step3，否则算 结束。 １３ 求强连通分量过程

3 对图进行深度优先搜索访问后进栈 DFN(u)为深度搜索的顺序。 基本图算法 强连通分量 DFN(u) 初始时 Tarjan算法 Low(u) min(Low[u],DFN[j]) (DFN(u)时刻 j 在栈中) min(Low[u],Low[j]) (DFN(u)时刻 j 不在栈中) 1 3 5 回朔时DFN(u)= Low(u)为强连通分量.出栈 DFN(u) Low(u) 1 2 3 4 5 6 1 1 2 4 6 6 5 6 2 2 1 栈 1 3 5 4 6 2 5 1 5 3 3 强连通分量： {6}, {5}, {1,3,4,2} 4 4 １５

4 强连通分量 1 3 5 Path Root 2 6 6 top 4 5 4 5 2 4 6 3 2 3 1 1 强连通分量： {6},
1、任意v结点开始访问，压入堆栈Path，Root。 对于它的邻接结点n： 基本图算法 强连通分量 2、若没有访问过，则以n为作用点，递归执行上述步骤。 Gabow算法 若访问过，而且没有确定它属于哪个强连通分量， Path中n之后所有的顶点从Root栈弹出 3、回朔时Root栈的有顶点元素v，在Path中取出 顶点v和之后顶点即强连通分量，删除Root中的v。 1 3 5 Path Root 2 6 6 top 4 5 4 5 2 4 6 3 2 3 1 1 强连通分量： {6}, {5}, {1,3,4,2} １６

5 强连通分量 Tarjan算法与Gabow算法作对比 1 = 3 Low(u)和DFN(u) 2 Root栈 5 作为是否为强连通分量的判断
Kosaraju算法 基本图算法 强连通分量 实现算法： Tarjan算法与Gabow算法作对比 Tarjan算法 Gabow算法 1 = 3 Low(u)和DFN(u) 2 Root栈 5 作为是否为强连通分量的判断 4 5 6 1,2,3,4 6 强连通分量： {6}, {5}, {1,3,4,2} １７