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

复杂网络中的社团发现算法对比和性能评估在复杂网络的研究中，社团发现算法对于揭示网络中隐含的组织结构和功能模块具有重要意义。

社团发现算法目的是将网络的节点划分为不同的社团或群集，使得同一个社团内的节点之间具有紧密的连接，而不同社团之间的连接则相对较弱。

本文将对几种常见的复杂网络社团发现算法进行对比和性能评估。

1. 强连通性算法强连通性算法主要关注网络中的强连通分量，即其中的节点之间互相可达。

常见的强连通性算法有Tarjan算法和Kosaraju算法。

这些算法适用于有向图和无向图，并且能够有效地识别网络中的全部强连通分量。

2. 谱聚类算法谱聚类算法是一种基于图谱理论的社团发现算法，通过将网络表示为拉普拉斯矩阵，使用特征值分解或近似方法提取主要特征向量，从而实现节点的划分。

常见的谱聚类算法包括拉普拉斯特征映射（LE）和归一化谱聚类（Ncut）。

谱聚类算法在复杂网络中表现出色，尤其在分割不规则形状的社团时效果较好。

3. 模块度优化算法模块度优化算法通过最大化网络的模块度指标，寻找网络中最优的社团划分。

常见的模块度优化算法有GN算法（Girvan-Newman）和Louvain算法。

这些算法通过迭代删除网络中的边或合并社团，以最大化模块度指标。

模块度优化算法具有较高的计算效率和准确性，广泛应用于实际网络的社团发现中。

4. 层次聚类算法层次聚类算法通过基于节点之间的相似度或距离构建层次化的社团结构。

常见的层次聚类算法有分裂和合并（Spectral Clustering，SC）和非重叠连通（Non-overlapping Connector，NC）算法。

这些算法通过自顶向下或自底向上的方式逐步划分或合并社团。

层次聚类算法能够全面地刻画网络中的社团结构，但在大规模网络上的计算复杂度较高。

5. 基于物理模型的算法基于物理模型的算法通过模拟物理过程来发现网络中的社团结构。

常见的基于物理模型的社团发现算法有模拟退火算法（Simulated Annealing，SA）和蚁群算法（Ant Colony Algorithm，ACA）。

离散数学试题及答案一、选择题1. 在集合论中，下列哪个选项表示两个集合A和B的并集？A. A ∩ BB. A ∪ BC. A - BD. A × B答案：B2. 命题逻辑中，下列哪个符号表示逻辑非？A. ∧B. ∨C. ¬D. →答案：C3. 在有向图中，如果存在一条从顶点u到顶点v的路径，那么称顶点v为顶点u的：A. 祖先B. 后代C. 邻居D. 连接点答案：B二、填空题1. 一个命题函数P(x)表示为“x是偶数”，那么其否定形式为________。

答案：x是奇数2. 在关系R上，如果对于所有的a和b，如果(a, b)∈R且(b, a)∈R，则称R为________。

答案：自反的三、简答题1. 简述什么是等价关系，并给出其三个基本性质。

答案：等价关系是一种特殊的二元关系，它满足自反性、对称性和传递性。

自反性指每个元素都与自身相关；对称性指如果a与b相关，则b也与a相关；传递性指如果a与b相关，b与c相关，则a与c也相关。

2. 解释什么是图的连通分量，并给出如何判断一个图是否是连通图。

答案：连通分量是指图中最大的连通子图，即图中任意两个顶点之间都存在路径。

判断一个图是否是连通图，可以通过深度优先搜索或广度优先搜索算法遍历整个图，如果所有顶点都被访问，则图是连通的。

四、计算题1. 给定命题公式P：((p → q) ∧ (r → ¬p)) → (q ∨ ¬r)，证明P是一个重言式。

答案：通过使用命题逻辑的等价规则和真值表，可以证明P在所有可能的p, q, r的真值组合下都为真，因此P是一个重言式。

2. 给定一个有向图G，顶点集合V(G)={1, 2, 3, 4}，边集合E(G)={(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)}。

找出所有强连通分量。

答案：通过Kosaraju算法或Tarjan算法，可以找到图G的强连通分量，结果为{1, 4}和{2, 3}。

求强连通分量的几种算法的实现与分析作者：陈燕,江克勤来源：《电脑知识与技术》2011年第09期摘要：有向图的强连通性是图论中的经典问题，有着很多重要的应用。

该文给出了求强连通分量的Kosaraju、Tarjan和Gabow三个算法的具体实现，并对算法的效率进行了分析。

关键词：强连通分量；深度优先搜索；Kosaraju算法；Tarjan算法；Gabow算法中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)09-2140-03The Implementation and Analysis of Several Algorithms About Strongly Connected Components CHEN Yan1, JIANG Ke-qin2(1.Nanjing Health Inspection Bureau, Nanjing 210003, China; 2.School of Computer and Information, Anqing Teachers College, Anqing 246011, China)Abstract: Digraph of strong connectivity is the classic problems in graph theory, which arises in many important applications. In this paper, the detailed implementation of Kosaraju, Tarjan and Gabow algorithms is discussed for solving strongly connected components, and the efficiency of three algorithms is analyzed.Key words: strongly connected components; depth first search; Kosaraju; Tarjan; Gabow图的连通性是图论中的经典问题，所谓连通性，直观地讲，就是“连成一片”。

求有向图的强连通分量的经典算法——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 的强联通分量。

强连通算法--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算法和Tarjan算法的比较一、定义在有向图中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。

如果有向图的每两个顶点都强连通，则称该有向图是一个强连通图。

非强连通的有向图的极大强连通子图，称为强连通分量(strongly connected components)。

而对于一个无向图，讨论强连通没有意义，因为在无向图中连通就相当于强连通。

由一个强连通分量内的所有点所组成的集合称为缩点。

在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该有向图的缩图。

例子：原图：缩图：上面的缩图中的缩点1包含：1、2,；缩点2包含：3；缩点3包含：4；缩点4包含：5、6、7。

二、求强连通分量的作用把有向图中具有相同性质的点找出来，形成一个集合（缩点），建立缩图，能够方便地进行其它操作，而且时间效率会大大地提高，原先对多个点的操作可以简化为对它们所属的缩点的操作。

求强连通分量常常用于求拓扑排序之前，因为原图往往有环，无法进行拓扑排序，而求强连通分量后所建立的缩图则是有向无环图，方便进行拓扑排序。

三、Kosaraju算法时间复杂度：O（M+N）注：M代表边数，N代表顶点数。

所需的数据结构：原图、反向图（若在原图中存在vi到vj的有向边，在反向图中就变成为vj到vi的有向边）、标记数组（标记是否遍历过）、一个栈（或记录顶点离开时间的数组）。

算法描叙：步骤1：对原图进行深度优先遍历，记录每个顶点的离开时间。

步骤2：选择具有最晚离开时间的顶点，对反向图进行深度优先遍历，并标记能够遍历到的顶点，这些顶点构成一个强连通分量。

步骤3：如果还有顶点没有遍历过，则继续进行步骤2，否则算法结束。

hdu1269（Kosaraju算法）代码：#include<cstdio>#include<cstdlib>const int M=10005;struct node{int vex;node *next;};node *edge1[M],*edge2[M];bool mark1[M],mark2[M];int T[M],Tcnt,Bcnt;void DFS1(int x)mark1[x]=true;node *i;for(i=edge1[x];i!=NULL;i=i->next) {if(!mark1[i->vex]){DFS1(i->vex);}}T[Tcnt]=x;Tcnt++;}void DFS2(int x){mark2[x]=true;node *i;for(i=edge2[x];i!=NULL;i=i->next) {if(!mark2[i->vex]){DFS2(i->vex);}}}int main(){int n,m;while(scanf("%d%d",&n,&m)){if(n==0&&m==0){break;}int i,a,b;for(i=1;i<=n;i++){mark1[i]=mark2[i]=false;edge1[i]=NULL;edge2[i]=NULL;}node *t;while(m--){scanf("%d%d",&a,&b);t=(node *)malloc(sizeof(node));t->vex=b;t->next=edge1[a];edge1[a]=t;t=(node *)malloc(sizeof(node));t->vex=a;t->next=edge2[b];edge2[b]=t;}Tcnt=0;for(i=1;i<=n;i++){if(!mark1[i]){DFS1(i);}}Bcnt=0;//Bcnt用于记录强连通分量的个数for(i=Tcnt-1;i>=0;i--){if(!mark2[T[i]]){DFS2(T[i]);Bcnt++;}}if(Bcnt==1)//如果强连通分量的个数为1则说明该图是强连通图{printf("Yes\n");}else{printf("No\n");}}return 0;}四、Tarjan算法时间复杂度：O（M+N）注：M代表边数，N代表顶点数。

求有向图的强连通分量个数（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、Kosaraju算法对每个不在树中的点开始DFS一次，并记录离开各点的时间，这里是离开的时间，而不是到达时的，比如有图1->2 2->3 则1,2,3分别对应的时间是3 2 1,因为3没有出边，所以最先离开，其次是2,最后是1,DFS后，在同一棵树中的点，如果dfn[v]>dfn[u]则说明点从v有可能到达u,而这棵树中的dfn[]最大的点，肯定可以到达每个点，从而在原图的逆图中，每次都选没有访问过的最大的dfn值开始DFS,如果可达点x 则说明它们是强连通的void DFS_T(int u){int i,v;if(used[u])return ;used[u]=1;id[u]=scc;for(i=q[u];i!=-1;i=Tedge[i].pre){v=Tedge[i].d;if(!used[v])DFS_T(v);}}void DFS(int v){int i,u;if(used[v])return ;used[v]=1;for(i=p[v];i!=-1;i=edge[i].pre){u=edge[i].d;if(!used[u])DFS(u);}order[++num]=v;}int Kosaraju(){int i,j,k,v,u;memset(used,0,sizeof(used));num=0;for(i=1;i<=n;++i)if(!used[i])DFS(i);memset(used,0,sizeof(used));memset(id,0,sizeof(id));scc=0;for(i=num;i>=1;--i)if(!used[order[i]])scc++,DFS_T(order[i]);}2、Tarjan算法dfn[v]记录到达点v的时间，跟上面的离开不同，low[v]表示通过它的子结点可以到达的所有点中时间最小值，即low[i]=min(low[i],low[u]),u为v的了孙，初始化时low[v]=dfn[u]。

环路识别算法
环路识别算法是指通过分析一个给定的网络或图结构，判断其中是否存在环路。

以下是几种常见的环路识别算法：
1. 深度优先搜索（DFS）：从一个节点开始进行深度优先搜索，记录访问过的节点并标记为已访问。

如果在搜索路径中遇到已访问的节点，则说明存在环路。

2. 广度优先搜索（BFS）：从一个节点开始进行广度优先搜索，使用队列来保存待访问的节点。

在搜索过程中，如果遇到已访问的节点，则说明存在环路。

3. 强连通分量算法：强连通分量是指一个图中的节点集合，其中的任意两个节点都可以相互到达。

通过使用强连通分量算法（如Tarjan算法或Kosaraju算法），可以将图划分为多个强连通分量。

如果存在一个强连通分量的大小大于1，则说明存在环路。

4. 拓扑排序：拓扑排序是一种对有向无环图（DAG）进行排序的算法。

在拓扑排序过程中，将入度为0的节点依次加入排序结果中，并将其邻接节点的入度减1。

如果最终排序结果包含所有的节点，则说明不存在环路；反之，存在环路。

这些算法可以根据具体的需求和应用场景进行选择和优化。

6.3.1强连通分⽀算法--Kosaraju算法、Tarjan算法和Gabow算法强连通分⽀算法本节内容将详细讨论有向图的强连通分⽀算法(strongly connected component)，该算法是图深度优先搜索算法的另⼀重要应⽤。

强分⽀算法可以将⼀个⼤图分解成多个连通分⽀，某些有向图算法可以分别在各个联通分⽀上独⽴运⾏，最后再根据分⽀之间的关系将所有的解组合起来。

在⽆向图中，如果顶点s到t有⼀条路径，则可以知道从t到s也有⼀条路径；在有向⽆环图中个，如果顶点s到t有⼀条有向路径，则可以知道从t到s必定没有⼀条有向路径；对于⼀般有向图，如果顶点s到t有⼀条有向路径，但是⽆法确定从t到s是否有⼀条有向路径。

可以借助强连通分⽀来研究⼀般有向图中顶点之间的互达性。

有向图G=(V, E)的⼀个强连通分⽀就是⼀个最⼤的顶点⼦集C，对于C中每对顶点(s, t)，有s和t是强连通的，并且t和 s也是强连通的，即顶点s和t是互达的。

图中给出了强连通分⽀的例⼦。

我们将分别讨论3种有向图中寻找强连通分⽀的算法。

3种算法分别为Kosaraju算法、Tarjan算法和Gabow算法，它们都可以在线性时间内找到图的强连通分⽀。

Kosaraju算法Kosaraju算法的解释和实现都⽐较简单，为了找到强连通分⽀，⾸先对图G运⾏DFS，计算出各顶点完成搜索的时间f；然后计算图的逆图GT，对逆图也进⾏DFS搜索，但是这⾥搜索时顶点的访问次序不是按照顶点标号的⼤⼩，⽽是按照各顶点f值由⼤到⼩的顺序；逆图DFS所得到的森林即对应连通区域。

具体流程如图(1~4)。

上⾯我们提及原图G的逆图GT，其定义为GT=(V, ET)，ET={(u, v):(v, u)∈E}}。

也就是说GT是由G中的边反向所组成的，通常也称之为图G的转置。

在这⾥值得⼀提的是，逆图GT和原图G有着完全相同的连通分⽀，也就说，如果顶点s和t在G中是互达的，当且仅当s和t在GT中也是互达的。

强连通分量个数的最小值1. 引言在图论中，强连通分量是指图中的一组顶点，其中任意两个顶点都存在一条有向路径。

强连通分量个数的最小值是指在一个有向图中，最少需要将多少个顶点组成一个强连通分量。

本文将介绍强连通分量的概念、计算方法以及如何求解强连通分量个数的最小值。

2. 强连通分量的定义在有向图中，如果从顶点A到顶点B存在一条有向路径，同时从顶点B到顶点A也存在一条有向路径，则称顶点A和顶点B是强连通的。

如果一个有向图中的每个顶点都与其他所有顶点强连通，则该有向图被称为强连通图。

而强连通分量则是指有向图中的一组顶点，其中任意两个顶点都是强连通的，且不与其他顶点强连通。

3. 强连通分量的计算方法为了计算一个有向图的强连通分量，可以使用强连通分量算法，其中最常用的是Tarjan算法和Kosaraju算法。

3.1 Tarjan算法Tarjan算法是一种深度优先搜索算法，用于寻找有向图的强连通分量。

算法的基本思想是通过DFS遍历图中的每个顶点，并记录每个顶点的遍历次序和能够到达的最小顶点次序。

通过这些信息，可以判断顶点是否属于同一个强连通分量。

具体步骤如下：1.初始化一个空栈和一个空的遍历次序数组。

2.对于每个未遍历的顶点，进行深度优先搜索。

3.搜索过程中，记录每个顶点的遍历次序和能够到达的最小顶点次序，并将顶点加入栈中。

4.当搜索完成后，根据遍历次序和能够到达的最小顶点次序，可以确定每个顶点所属的强连通分量。

3.2 Kosaraju算法Kosaraju算法是另一种用于计算有向图强连通分量的算法。

算法的基本思想是通过两次深度优先搜索来确定强连通分量。

具体步骤如下：1.对原始图进行一次深度优先搜索，记录顶点的遍历次序。

2.对原始图的转置图（即将所有边的方向反转）进行一次深度优先搜索，按照遍历次序对顶点进行访问。

3.访问过程中，可以确定每个顶点所属的强连通分量。

4. 求解强连通分量个数的最小值要求解强连通分量个数的最小值，可以使用以下方法：1.使用Tarjan算法或Kosaraju算法计算有向图的强连通分量。

寻找强连通分量的方法和证明嘿，咱今儿就来唠唠寻找强连通分量的那些事儿！你知道吗，这强连通分量就像是一个小团体，里面的元素那可是紧密相连啊！就好比一群好朋友，不管谁跟谁都能说得上话，互相都有关系。

那怎么找到这些小团体呢？有一种方法叫 Kosaraju 算法。

这就好像是我们在一个大迷宫里找特定的区域，先顺着一条路走，标记好走过的地方，然后再换个方向走，看看哪些地方是能来回都能走到的，那些就是强连通分量啦！它先对图进行深度优先搜索，然后再把图反转过来，再进行一次深度优先搜索，嘿，神奇吧，这样就能把那些小团体给揪出来啦！还有 Tarjan 算法呢！这就像是一个超级侦探，一点点地去挖掘线索，把那些隐藏的强连通分量给找出来。

它通过巧妙地利用栈和一些标记，就能准确地找到这些紧密相连的部分。

那怎么证明这些算法是有效的呢？这就好像我们要证明一件事情是对的一样。

我们可以从它们的原理出发，看看是不是真的能把该找的都找到，而且不会找错。

就像我们检查自己的作业一样，要仔细认真，不能有一点儿马虎。

你想想看，如果这些算法不靠谱，那我们岂不是白费力气？那可不行！所以证明它们的有效性是非常重要的呀！比如说，我们可以用一些特殊的例子来测试，看看是不是每次都能准确找到强连通分量。

如果都能找到，那说明这个算法厉害呀！而且啊，这些算法可不是随便想出来的，那是经过很多聪明的脑袋瓜琢磨出来的呢！他们就像一群勇敢的探险家，在数学的海洋里不断探索，终于找到了这些宝藏般的方法。

你再想想，要是没有这些方法，我们面对那些复杂的图该怎么办呀？岂不是要抓瞎啦！所以说呀，这些方法和证明可太重要啦！我们在学习这些的时候，可不能死记硬背哦！要理解它们背后的原理，就像理解朋友的心思一样。

只有这样，我们才能真正掌握这些知识，在需要的时候能拿出来用。

哎呀呀，寻找强连通分量的方法和证明，真的是太有意思啦！它们就像一把钥匙，能打开那神秘的图的世界，让我们看到其中的奥秘和精彩。

典型算法与ACM题目解析(02)—有向图的强连通分量上一篇:典型算法与ACM题目解析(01)—寻找最大流的标号法下一篇:关于STL中优先队列的用法作者:dzf 阅读次数:87 时间:2006-11-27 21:23:49 算法园地这道题是POJ的2186题，题意是说，有一群牛，总数为N(N<=10000),题目数据给出牛之间的关系，比如说1仰慕2，2仰慕3等等，设这种仰慕是可以传递的，如果1仰慕2，那么1也会同时仰慕2仰慕的那些牛，如果一头牛被所有的牛都仰慕，那么它将是最受欢迎的牛，题目要求的是有多少牛是"最受欢迎的"。

这道题目大家第一眼看到可能感觉直接模拟，但是由于数据量巨大，模拟的话肯定是过不了的，而且题目中还会出现环路的情况，比如1=>2,2=>3,3=>1，所以这解这道题最好的方法是使用有向图的强连通分量。

在同一个强连通分量里的所有的牛之间是互相仰慕的，我们将其缩为一点，并且只记录这一点的牛的数量，如果有最受欢迎的牛存在，那么这个图将是连通图，并且出度为零的点只有一个，我们可以用并查集来判是否连通，然后计算每个节点的出度，即可求出最受欢迎的牛的数量。

求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，其中Kosaraju算法要对原图和逆图都进行一次DFS，而另外两种算法只要DFS一次就可以了用了Gabow算法和Kosaraju算法各写了一遍在时间上Gabow算法是122ms,Kosaraju算法是61ms理论上Gabow算法要比Kosaraju快些的，因为Gabow算法只对原图进行一次DFS而Kosaraju要进行两次Gabow反而慢的原因可能是我用了STL里的stackPS:我没看懂Gabow算法，完全是对着书上写的代码如下:Kosaraju算法/*求有向图的强连通分量的Kosaraju‘s algorit hmBy Sempr ---- 2006.06.16*/#include <stdio.h>#include <string.h>#define G_size 100000#define V_size 11000typedef struct Graph{int id;int next;} Graph;typedef struct Edge{int s, e;} Edge;Edge E[G_size];Graph GA[G_size], GT[G_size];int N, M;int G_end;int order[V_size], id[V_size], vis[V_size], in[V_size]; int cnt, scnt, pos;void Insert(int s, int e) //建立原图和逆图{int p;p = s;while (GA[p].next)p = GA[p].next;GA[G_end].id = e;GA[p].next = G_end;p = e;while (GT[p].next)p = GT[p].next;GT[G_end].id = s;GT[p].next = G_end;G_end++;}void DFST(int x) //对逆图进行搜索{int p, q;vis[x] = 1;p = GT[x].next;while (p){q = GT[p].id;if (!vis[q])DFST(q);p = GT[p].next;}order[cnt++] = x;}void DFSA(int x) //对原图进行搜索{int p, q;vis[x] = 1;id[x] = cnt;p = GA[x].next;while (p){q = GA[p].id;if (!vis[q])DFSA(q);p = GA[p].next;}}void Solve() //主要过程{int s, e;int i;memset(GA, 0, sizeof(GA));memset(GT, 0, sizeof(GT));memset(E, 0, sizeof(E));G_end = N + 1;for (i = 0; i < M; i++){scanf("%d %d", &s, &e);E[i].s = s - 1;E[i].e = e - 1;Insert(s - 1, e - 1); }memset(vis, 0, sizeof(vis));cnt = 0;for (i = 0; i < N; i++){if (!vis[i]){DFST(i);}}memset(vis, 0, sizeof(vis));cnt = 0;for (i = N - 1; i >= 0; i--){if (!vis[order[i]]){DFSA(order[i]);cnt++;}}for (i = 0; i < M; i++){s = id[E[i].s];e = id[E[i].e];if (s != e){in[s]++;}}scnt = cnt;cnt = 0;for (i = 0; i < scnt; i++){if (in[i] == 0)pos = i;cnt++;}}if (cnt != 1){printf("0\n");}else{cnt = 0;for (i = 0; i < N; i++){if (in[id[i]] == pos){cnt++;}}printf("%d\n", cnt);}}int main(){while (EOF != scanf("%d %d", &N, &M))Solve();return 0;}Gabow算法/*求有向图的强连通分量的Gabow‘s algorithmBy Sempr ---- 2006.06.14*/#include <stdio.h>#include <algorithm>#include <stack>#define size 11000using namespace std;int N, M;typedef struct Node{int next;} Node;typedef struct Edge{int s, e;}Edge;Edge E[size * 6];Node G[size * 7];int pre[size], id[size];typedef stack<int> Stack;Stack S, path;int end;int cnt, scnt;int vis[size];int in[size];void Insert(int s, int e){int p = s;while (G[p].next){p = G[p].next;if (G[p].id == e){return;}}G[p].next = end;G[end].id = e;end++;}void scR(int w){int v;int p, t;pre[w] = cnt++;S.push(w);path.push(w);p = G[w].next;while (p){t = G[p].id;p = G[p].next;if (pre[t] == -1)scR(t);else if (id[t] == -1)while (pre[path.top()] > pre[t])path.pop();}if (path.top() == w)path.pop();elsereturn;do{id[v = S.top()] = scnt;S.pop();}while (v != w);scnt++;}void Gabow(){int i;memset(pre, -1, sizeof(pre));memset(id, -1, sizeof(id));cnt = 0;scnt = 0;while (!S.empty())S.pop();while (!path.empty())path.pop();for (i = 1; i <= N; i++){if (pre[i] == -1){scR(i);}}}void DFS(int w, int d){int p = G[w].next;d++;pre[w] = 1;if (d > cnt){cnt = d;}while (p){if (pre[G[p].id] != 1){DFS(G[p].id, d);}p = G[p].next;}}void Solve(){int i, s, e;int pos;memset(G, 0, sizeof(G));end = N + 10;memset(in, 0, sizeof(in));for (i = 0; i < M; i++){scanf("%d %d", &s, &e);E[i].s = s;E[i].e = e;Insert(s, e);}Gabow();memset(G, 0, sizeof(G));memset(pre, 0, sizeof(pre));end = scnt + 10;for (i = 0; i < M; i++){s = id[E[i].s];e = id[E[i].e];if (s != e){in[s]++;}}cnt = 0;for (i = 0; i < scnt; i++){if (in[i] == 0){pos = i;cnt++;}}if (cnt != 1){printf("0\n");}else{cnt = 0;for (i = 1; i <= N; i++){if (in[id[i]] == pos){cnt++;}}printf("%d\n", cnt);}}int main(){while (scanf("%d %d", &N, &M) != EOF)Solve();}return 0;}。

强连通分量强连通分量的三种算法有：1. Kosaraju算法（双DFS）2.Tarjan3.Gabow一．Tarjan1.解释1文章分类:C++编程1,在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。

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

非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected component)。

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

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

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

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

定义几个关键数组:int DFN[MAX]; //记录节点u第一次被访问时的步数int LOW[MAX]; //记录与节点u和u的子树节点中最早的步数接下来是对算法流程的演示。

从节点1开始DFS，把遍历到的节点加入栈中。

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

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

返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。

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

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

节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。

继续回到节点1，最后访问节点2。

访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。

返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。

至此，算法结束。

经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

Kosaraju算法Kosaraju算法基于以下思想：强连通分量一定是某种DFS形成的DFS树森林。

Kosaraju 算法给出了更具体的方式：①任意进行一次DFS，记录下每个节点的结束时间戳f[i]。

②按f[i]的大小对节点进行排序（从小到大）。

③以②的排序结果为顺序再进行一次DFS，所得的DFS树森林即为强连通分量。

这次DFS 可以用Floodfill进行，把每个强连通分量标上不同序号。

（这就是OI界传说中的“求强连两遍DFS的算法”）比如上图，我们可以得到：d[1]=1 f[1]=14d[2]=2 f[2]=5d[3]=6 f[3]=13d[4]=3 f[4]=4d[5]=7 f[5]=8d[6]=9 f[6]=12d[7]=10 f[7]=11根据f[i]排序得：④②⑤⑦⑥③①（发现了什么？就是后序遍历），再按照这个顺序进行DFS 即可。

程序：var a:array[1..1000,1..1000]of longint;b,flag:array[1..1000]of longint;n,i,j,m,k:longint;procedure dfs(x:longint);var j:longint;beginflag[x]:=1;for j:=1 to n doif (flag[j]=0)and(a[x,j]>0) then dfs(j);inc(m);b[m]:=x;end;procedure fill(x,k:longint);var j:longint;beginflag[x]:=k;for j:=n downto 1 doif (flag[b[j]]=0)and(a[b[j],x]>0) then fill(b[j],k);end;beginreadln(n);for i:=1 to n dobeginfor j:=1 to n do read(a[i,j]);readln;end;m:=0;fillchar(flag,sizeof(flag),0);for i:=1 to n doif flag[i]=0 then dfs(i);fillchar(flag,sizeof(flag),0);k:=0;for i:=n downto 1 doif flag[b[i]]=0 thenbegininc(k);fill(b[i],k);end;for i:=1 to k dobeginfor j:=1 to n doif flag[j]=i then write(j,' ');writeln;end;end.Tarjan算法Tarjan算法只要一遍DFS，效率高于Kosaraju。

有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量(S trongly Connected Component, SCC)最关键通用部分：强连通分量一定是图的深搜树的一个子树。

一、Kosaraju算法1. 算法思路基本思路：这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。

(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通分量。

余下部分和原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。

改进思路：当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。

想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于GT来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。

这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i] =j。

那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。

每次深搜都得到一个强连通分量。

隐藏性质:分析到这里，我们已经知道怎么求强连通分量了。

但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。

连通分量（tarjan算法）对于有向图中，连通分量叫强连通分量对于⽆向图中，连通分量叫双连通分量，⽽在双连通分量中，⼜分为点双连通和边双连通。

重点讨论双连通的情况：以割点区分连通情况的双连通叫做点双连通分量，以割边区分连通情况的双连通叫做边双连通分量。

⽐如这个图中：1 4| \ / \| \ / \| 2 5| / \ /| / \ /3 6如果要的到两个连通分量的话，我们只有以2节点为割点，将图分为点双连通。

我们便可以得到两个双连通分量(1,2,3)、(2,4,5,6)。

再⽐如这个图：1 5| \ / \| \ / \| 2 — 4 6| / \ /| / \ /3 7如果要得到两个连通分量的话，我们只能以(2,4)边为割边，得到两个边双连通分量。

具体是将⼀个⽆向图分成点双连通还是边双连通得看具体的问题。

下⾯具体讨论⼀下⽤tarjan算法实现起来的区别。

1、对于边双连通分量，由于是以边为连通间的区分，那么每个点只属于⼀个连通分量，我们在深度遍历的时候，只需要记录某⼀点是否被访问即可。

2、但是对于点双连通分量，由上图也可以看出，2节点同时属于两个连通分量，如果还是以节点为重判对象的话，将得到错误的答案。

此时，我们应该以边为重判对象，⽽该边的两个端点，都同属于⼀个点双连通。

对于边双连通的实现，由于没有节点会重复属于两个以上的连通分量，所以我们可以先简单的遍历⼀遍整个图的tarjan标号(low、dnf)。

之后再进⾏⼀次深度遍历，以low[v]>dnf[u]为换⾊标准染⾊，最后每种颜⾊即⼀个分量。

代码：void tarjan(int u,int f) //f为⽗节点{low[u]=dnf[u]=++count;visit[u]=1;S.push(u);for(node *p=link[u];p;p=p->next){if(p->v==f)continue;if(!visit[p->v]) //⼀节点为重判对象{tarjan(p->v,u);if(low[u]>low[p->v]){low[u]=low[p->v];}}else if(low[u]>dnf[p->v])low[u]=dnf[p->v];}}void set_color(int u){for(node *p=link[u];p;p=p->next){if(!color[p->v]){if(low[p->v]>dnf[u]) //找到了关键割边，换⼀种颜⾊染⾊color[p->v]=++cut;elsecolor[p->v]=color[u]; //保持原来的颜⾊set_color(p->v);}}}对于点双连通的实现，经过上⾯的分析，由于存在点既属于A分量⼜属于B分量，所有我们此时采纳边为重判对象，⽽该边的两端点同属于⼀个分量代码：void col(int u){int x;node *p;++cut;do{p=stack[--top];color[p->v]=color[p->op->v]=cut;}while(p->op->v!=u);}void tarjan(int u){low[u]=dnf[u]=++cut;for(node *p=link[u];p;p=p->next){if(p->vist) //该边已被访问continue;p->vist=p->op->vist=1; //两个⽅向都标记已访问stack[top++]=p; //该边进栈if(!dnf[p->v]){tarjan(p->v);if(low[u]>low[p->v])low[u]=low[p->v];if(low[p->v]>=dnf[u]) //找到了关键割点col(u);}else if(low[u]>dnf[p->v])low[u]=dnf[p->v];}}。

Kosaraju算法详解Kosaraju算法可以求出有向图中的强连通分量个数，并且对分属于不同强连通分量的点进⾏标记。

它的算法描述较为简单：(1) 第⼀次对图G进⾏DFS遍历，并在遍历过程中，记录每⼀个点的退出顺序。

以下图为例：如果以1为起点遍历，访问结点的顺序如下：结点第⼆次被访问即为退出之时，那么我们可以得到结点的退出顺序：(2)倒转每⼀条边的⽅向，构造出⼀个反图G’。

然后按照退出顺序的逆序对反图进⾏第⼆次DFS遍历。

我们按1、4、2、3、5的逆序第⼆次DFS遍历：访问过程如下：每次遍历得到的那些点即属于同⼀个强连通分量。

1、4属于同⼀个强连通分量，2、3、5属于另⼀个强连通分量。

代码：1 #include<iostream>2 #include<cstdio>3 #include<cstring>4using namespace std;5int map[101][101];6int nmap[101][101];7int pass[101];8int vis[101];9int now=1;10int n,m;11int num=0;12void dfs(int p)13 {14 vis[p]=1;15for(int i=1;i<=n;i++)16 {17if(vis[i]==0&&map[p][i]==1)18 {19 dfs(i);2021 }22 }23 pass[now]=p;24 now++;25 }26void ndfs(int p)27 {28 vis[p]=0;29for(int i=1;i<=n;i++)30 {31if(vis[i]==1&&nmap[p][i]==1)32 ndfs(i);33 }34 }35int main()36 {3738 scanf("%d%d",&n,&m);39for(int i=1;i<=m;i++)40 {41int x,y;42 scanf("%d%d",&x,&y);43 map[x][y]=1;44 nmap[y][x]=1;45 }46for(int i=1;i<=n;i++)47 {48if(vis[i]==0)49 dfs(i);50 }51 pass[now]=1;52for(int i=n;i>=1;i--)53 {54if(vis[pass[i]]==1)55 {56 ndfs(pass[i]);57 num++;58 }59 }60 cout<<num;61return0;62 }。