有向图强连通分量无向图双连通分量.ppt

有向图强连通分量无向图双连通分量 定义 下面给出强连通分量的定义： 有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量 Strongly Connected Component，简称SCC 根据定义，在上题中，一组互相仰慕的牛就构成了一个强连通分量（一个大牛）。 强连通分量算法 求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，时间复杂度均为o（n+e）。 其中Kosaraju算法要对原图和逆图都进行一次DFS，另外两种算法只要DFS一次， Gabow算法是Tarjan算法的改进。 下面简单介绍Kosaraju算法。 Kosaraju算法（黑书286） 算法步骤(正确性证明略) 对有向图进行DFS，记录下顶点变黑的时间A[i]。 改变图G 的每一条边的方向，生成新图GT。 按上次DFS 顶点变黑的时间A[i]由大到小顺序对GT进行DFS。遍历结果构成森林W 。 W 中每棵树的结点构成了有向图的一个强连通分量。 DFS 在演示之前，重新介绍DFS深度优先有哪些信誉好的足球投注网站为结点着色以表示结点的状态的过程。 每个顶点开始均为白色。 有哪些信誉好的足球投注网站中被发现时置为灰色。 结束时又被置成黑色(即当其邻接表被完全检索之后)。 演示 对G进行dfs，记录下顶点变黑时间A[i]。 得到A[i]从大到小的顺序： F G A C D E B A (5) B(1) C(4) D(3) E(2) F(7) G(6) 演示 改变图G 的每一条边的方向，生成新图GT 按A[i]由大到小顺序F G A C D E B对GT进行第二次DFS 得到森林w FG||ACB||DE A (5) B(1) C(4) D(3) E(2) F(7) G(6) 演示 根据森林w FG||ACB||DE 由每个强连通分量为有哪些信誉好的足球投注网站树中的一棵子树。 得到已拓扑有序的强连通分量 S2||S1||S3 A B C D E F G S1 S3 S2 Tarjan_Algorithm 任何一个强连通分量，必定是对原图的深度优先有哪些信誉好的足球投注网站树的子树。 Tarjan思想 我们首先要确定每个强连通分量的子树的根。然后从这些根出发找到强连通分量。 Tarjan_Algorithm 在这里我们维护两个数组，一个是A[1..n]，一个是minlink[1..n]。 A[i]表示顶点i开始访问时间。 minlink [i]为与顶点i邻接的顶点未删除顶点j的minlink [j]和minlink [i]的最小值 (minlink[i]初始化为A[i])。 Tarjan_Algorithm 这样，在一次深搜的回溯过程中，如果发现minlink[i]==A[i]那么，当前顶点就是一个强连通分量的根 。 而当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。 Tarjan_Algorithm step1: 找一个没有被访问过的节点v，goto step2(v)。否则，算法结束。 step2(v): 初始化indx[v]和mlik[v] 对于v所有的邻接顶点u： 1) 如果没有访问过，则step2(u),同时维护mlik[v] 2) 如果访问过，但没有删除，维护mlik[v] 如果indx[v]==mlik[v]，那么输出相应的强连通分量 ? ??? ?在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。一个图的点连通度的定义为，最小割点集合中的顶点数。 ??? ???? 类似的，如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。一个图的边连通度的定义为，最小割边集合中的边数。 点连通度与边连通度 双连通图、割点与桥 ? ????如果一个无向连通图的点连通度大于1，则称该图是点双连通的(point biconnected)，简称双连通或重连通。一个图有割点，当且仅当这个图的点连通度为1，则割点集合的唯一元素被称为割点(cut point)，又叫关节点(articulation point)。 ? ????如果一个无向连通图的边连通度大于1，则称该图是边双连通的(edge biconnected)，简称双连通或重连通。一个图有桥，当且仅当这个图的边连通度为1，则割边集合的唯一元素被称为桥(bridge)，又叫关节边(articulation edge)。 ? ????可以看出，点双连通与边双连通都可以简称为双连通，它们之间是有着某种联系的，下文中提到的双连通，均既可指点双连通，又可指边双连通。