有向图的强连通分量

连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。

块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。

缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。

求块跟求缩点非常相似，很容易搞混，但本质上完全不同。

割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。

有割点的图不一定有割边，如：3是割点，分别与(1,2)和(4,5)形成两个无割点的块有割边的图也不定有割点,如：w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。

dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。

low[i]=min(low[i],dfn[son[i]])设 v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。

如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。

求有向图的强连通分量的经典算法——Kosaraju算法一、Kosaraju算法步骤：Step1、对有向图G做dfs（深度优先遍历），记录每个结点结束访问的时间Step2、将图G逆置，即将G中所有弧反向。

Step3、按Step1中记录的结点结束访问时间从大到小对逆置后的图做dfs Step4、得到的遍历森林中每棵树对应一个强连通分量。

相关概念：在dfs(bfs)算法中，一个结点的开始访问时间指的是遍历时首次遇到该结点的时间，而该结点的结束访问时间则指的是将其所有邻接结点均访问完的时间。

二、Kosaraju算法求解过程实例下面结合实例说明Kosaraju算法的基本策略。

图1给出了一个有向图G。

图1 有向图GStep1：假设从DFS在遍历时按照字母顺序进行，根据Kosaraju算法，在步骤1中我们得到的遍历顺序可以表达为[A,[C,[B,[D,D],B],C],A][E,[F,[G,[H,H],G],F],E]在遍历序列中每一个结点出现了两次，其中第一次出现的时间为该结点的开始访问时间，第二次出现的时间为该结点的结束访问时间。

Step2：根据算法第2步，将图G逆置，得到对应的反向图G’如图2所示。

Step3：根据步骤1得到的遍历序列，按照结点结束访问时间递减排序后的结果为EFGHACBD下面，按照该结点序列顺序对逆置图G ’所深度优先遍历，得到的深度优先遍历森林如图3所示。

森林中共有4棵树，其中(a)和(d)只有一个结点，这里认为单结点也是一个强联通分量（在实际应用中可以根据实际需要将这种情况过滤掉）。

三、算法讨论问题1：以上图为例，第一遍搜索得到以A 为根的子序列（设为S1）和以E 为根的子树序列（设为S2），图反向后，再从E 开始搜索，能搜到的元素肯定不会包含S1的元素，为什么？答：因为S1中的点都不能到达E ，而第二遍搜索就是看哪些点能到达E ，所以搜不到S1中的点。

问题2：图反向后对A 进行深搜，尽管E 能到达A ，为什么搜不到E ？因为第一遍深搜时，A 不能达到E ，所以E 肯定位于A 的右边，而第二遍深搜是按照结束时间进行搜索的，在搜索A 之前，已经搜完E ，对E 设置了已经遍历标志，所以不会把E 并入A 的强联通分量。

强连通分量（超详细）⼀、定义在有向图G中，如果两个顶点u，ｖ间有⼀条从ｕ到ｖ的有向路径，同时还有⼀条从ｖ到ｕ的有向路径，则称两个顶点强连通。

如果有向图G的每两个顶点都强连通，称G是⼀个强连通图。

有向⾮强连通图的极⼤强连通⼦图，称为强连通分量。

图中，⼦图{1,2,3,4}为⼀个强连通分量，因为顶点1,2,3,4两两可达。

{5},{6}也分别是两个强连通分量。

⼆、tarjan算法时间复杂度是O(N+M)四条边：树枝边：DFS时经过的边，即DFS搜索树上的边。

前向边：与DFS⽅向⼀致，从某个结点指向其某个⼦孙的边。

后向边：与DFS⽅向相反，从某个结点指向其某个祖先的边。

（返祖边）横叉边：从某个结点指向搜索树中的另⼀⼦树中的某结点的边。

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的⼀棵⼦树。

搜索时，把当前搜索树中未处理的节点加⼊⼀个堆栈，回溯时可以判断栈顶到栈中的节点是否为⼀个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的⼦树能够追溯到的最早的栈中节点的次序号。

由定义可以得出，Low(u)=Min {Low(u), Low(v) } (u,v)为树枝边，u为v的⽗节点 . Low(u)=Min {Low(u), DFN(v) } DFN(v),(u,v)为指向栈中节点的后向边(指向栈中结点的横叉边) }当结点u搜索结束后，若DFN(u)=Low(u)时，则以u为根的搜索⼦树上所有还在栈中的节点是⼀个强连通分量。

算法过程：从节点1开始DFS，把遍历到的节点加⼊栈中。

搜索到节点u=6时，DFN[6]=LOW[6]，找到了⼀个强连通分量。

退栈到u=v为⽌，{6}为⼀个强连通分量。

初始化时Low[u]=DFN[u]=++index返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为⼀个强连通分量。

返回节点3，继续搜索到节点4，把4加⼊堆栈。

发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。

强连通算法--Tarjan个⼈理解+详解⾸先我们引⼊定义：1、有向图G中，以顶点v为起点的弧的数⽬称为v的出度，记做deg+（v）；以顶点v为终点的弧的数⽬称为v的⼊度，记做deg-（v）。

2、如果在有向图G中，有⼀条<u，v>有向道路，则v称为u可达的，或者说，从u可达v。

3、如果有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使得u不能到v，或者v不能到u，则称图G 是强⾮连通图。

4、如果有向图G不是强连通图，他的⼦图G2是强连通图，点v属于G2，任意包含v的强连通⼦图也是G2的⼦图，则乘G2是有向图G的极⼤强连通⼦图，也称强连通分量。

5、什么是强连通？强连通其实就是指图中有两点u，v。

使得能够找到有向路径从u到v并且也能够找到有向路径从v到u，则称u，v是强连通的。

然后我们理解定义：既然我们现在已经了解了什么是强连通，和什么是强连通分量，可能⼤家对于定义还是理解的不透彻，我们不妨引⼊⼀个图加强⼤家对强连通分量和强连通的理解：标注棕⾊线条框框的三个部分就分别是⼀个强连通分量，也就是说，这个图中的强连通分量有3个。

其中我们分析最左边三个点的这部分：其中1能够到达0,0也能够通过经过2的路径到达1.1和0就是强连通的。

其中1能够通过0到达2,2也能够到达1，那么1和2就是强连通的。

.........同理，我们能够看得出来这⼀部分确实是强连通分量，也就是说，强连通分量⾥边的任意两个点，都是互相可达的。

那么如何求强连通分量的个数呢？另外强连通算法能够实现什么⼀些基本操作呢？我们继续详解、接着我们开始接触算法，讨论如何⽤Tarjan算法求强连通分量个数：Tarjan算法，是⼀个基于Dfs的算法（如果⼤家还不知道什么是Dfs，⾃⾏百度学习），假设我们要先从0号节点开始Dfs，我们发现⼀次Dfs 我萌就能遍历整个图（树），⽽且我们发现，在Dfs的过程中，我们深搜到了其他强连通分量中，那么俺们Dfs之后如何判断他喵的哪个和那些节点属于⼀个强连通分量呢？我们⾸先引⼊两个数组：①dfn【】②low【】第⼀个数组dfn我们⽤来标记当前节点在深搜过程中是第⼏个遍历到的点。

求有向图的强连通分量个数（kosaraju算法）求有向图的强连通分量个数（kosaraju算法）1. 定义连通分量：在⽆向图中，即为连通⼦图。

上图中，总共有四个连通分量。

顶点A、B、C、D构成了⼀个连通分量，顶点E构成了⼀个连通分量，顶点F，G和H，I分别构成了两个连通分量。

强连通分量：有向图中，尽可能多的若⼲顶点组成的⼦图中，这些顶点都是相互可到达的，则这些顶点成为⼀个强连通分量。

上图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。

2. 连通分量的求解⽅法对于⼀个⽆向图的连通分量，从连通分量的任意⼀个顶点开始，进⾏⼀次DFS，⼀定能遍历这个连通分量的所有顶点。

所以，整个图的连通分量数应该等价于遍历整个图进⾏了⼏次（最外层的）DFS。

⼀次DFS中遍历的所有顶点属于同⼀个连通分量。

下⾯我们将介绍有向图的强连通分量的求解⽅法。

3. Kosaraju算法的基本原理我们⽤⼀个最简单的例⼦讲解Kosaraju算法显然上图中有两个强连通分量，即强连通分量A和强连通分量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。

每个连通分量中有若⼲个可以相互访问的顶点（这⾥都是3个），强连通分量与强连通分量之间不会形成环，否则应该将这些连通分量看成⼀个整体，即看成同⼀个强连通分量。

我们现在试想能否按照⽆向图中求连通分量的思路求解有向图的强连通分量。

我们假设，DFS从强连通分量B的任意⼀个顶点开始，那么恰好遍历整个图需要2次DFS，和连通分量的数量相等，⽽且每次DFS遍历的顶点恰好属于同⼀个连通分量。

但是，我们若从连通分量A中任意⼀个顶点开始DFS，就不能得到正确的结果，因为此时我们只需要⼀次DFS就访问了所有的顶点。

所以，我们不应该按照顶点编号的⾃然顺序（0,1,2，……）或者任意其它顺序进⾏DFS，⽽是应该按照被指向的强连通分量的顶点排在前⾯的顺序进⾏DFS。

上图中由强连通分量A指向了强连通分量B。

强联通分量与模拟链表作者：逸水之寒1.强连通分量强连通分量的定义是：在有向图中，u可以到达v，但是v不一定能到达u，如果u,v 到达，则他们就属于一个强连通分量。

求强连通分量最长用的方法就是Kosaraju算法，比较容易理解而且效率很高，本文对强连通分量的求法均采用Kosaraju算法。

其主要思想：首先对原图G进行深搜形成森林（树），然后选择一棵树进行第二次深搜，注意第一次是要判断节点A能不能通向节点B，而第二次要判断的是节点B能不能通向A，能遍历到的就是一个强连通分量。

（附录给出伪代码）Kosaraju算法如果采用了合适的数据结构，它的时间复杂度是O(n)的。

相关题目有很多，例如USACO 5.3.3，2009NOIP Senior No.3。

下面将以USACO 5.3.3 schlnet 举例说明。

Preblem 1. Network of Schools (USACO 5.3.3 schlnet\IOI96 No.3)A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the "receiving schools"). Note that ifB is in the distribution list of school A, then A does not necessarily appear in the list of school B.You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.INPUT FORMATThe first line of the input file contains an integer N: the number of schools in the network (2<=N<=100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.SAMPLE INPUT (file schlnet.in)52 43 04 5 01 0OUTPUT FORMATYour program should write two lines to the output file. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.SAMPLE OUTPUT (file schlnet.out)12分析：本题需要将强连通分量进行缩点，具体做法可以先求出所有的强连通分量，然后重新建立图，将一个强连通分量用一个点在新图中表示出来。

一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A)1/2 B)1 C)2 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A)1/2 B)1 C)2 D)4B03、有8个结点的无向图最多有条边。

A)14 B)28 C)56 D)112C04、有8个结点的无向连通图最少有条边。

A)5 B)6 C)7 D)8C05、有8个结点的有向完全图有条边。

A)14 B)28 C)56 D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、图的深度优先遍历类似于二叉树的。

A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历D14、图的广度优先遍历类似于二叉树的。

ab edcf第七章图一、选择题1．图中有关路径的定义是（）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列C．由不同边所形成的序列 D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn；4．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）5．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

A．1/2 B．2 C．1 D．46．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表7．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图 B．无向图 C．AOV网 D．AOE网8. 设如左图所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）a eb d fc a c fde b a e df c b a e fd c b aef d b cA．5个 B．4个 C．3个 D．2个9．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径10. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。

（1）．A．VT，ET为空 B．VT为所有顶点，ET为空C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小B．选i属于VT，j不属于VT，且（i，j）上的权最大C．选i不属于VT，j不属于VT，且（i，j）上的权最小D．选i不属于VT，j不属于VT，且（i，j）上的权最大（3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET（4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解11. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ；（图用邻接矩阵表示）(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。

强连通分量的定义
强连通分量是图论中的一个概念，指的是在有向图中，若任意两个顶点都存在一条有向路径，则这个有向图就是强连通的。

而强连通分量则指的是有向图中的极大强连通子图，即在该子图中任意两个顶点都是强连通的，并且该子图不能再加入其他的顶点或边使其仍然保持强连通。

在实际应用中，强连通分量有着广泛的应用。

比如在电路设计中，可以将电路看作一个有向图，每个元件看作一个顶点，元件之间的电线则看作一条有向边。

那么在这个电路中，如果存在一个强连通分量，则说明这些元件可以构成一个独立的电路模块，可以方便地进行测试和维护。

此外，在社交网络分析、路网规划等领域，强连通分量也有着重要的应用。

在实际应用中，我们可以通过深度优先搜索（DFS）或者Tarjan算法来求解一个有向图的强连通分量。

具体来说，DFS 算法可以通过遍历有向图来寻找所有的强连通分量；而Tarjan 算法则是一种更高效的算法，可以在O(V+E)的时间复杂度内求解一个有向图的所有强连通分量。

总之，强连通分量是图论中一个重要的概念，在实际应用中有着广泛的应用。

通过深入学习和理解这个概念，我们可以更好地应用它来解决实际问题。