寻找无向图的连通图使用深度优先搜索，您可以轻松找到图的所有连通图。回想一下连通图的概念：如果存在从任何顶点到任何顶点的路径，则称该图是连通的。连通分量是指图中所有最大连通的子图。如果把整个图比作一根串着珠子的绳子，任何一个顶点被抬起，连通图就是一个整体；非连通图会分散成几个更小的整体，每个整体都是整个图的连通分量。很容易知道，一张连通图只有一个连通分量，就是它自己；如果一个图的顶点是分散的，那么连通分量（只有一个顶点）的个数就是这个图的顶点个数。因此，连通分量的数量范围从[1,graph.vertexNum]到下图，它有3个连通分量。回忆一下深度优先搜索的过程：它从某个顶点开始，访问它的一个相邻点，然后访问这个相邻点的某个相邻点……如此深入，直到到达某个顶点，它找到即周围的邻接点已经被访问过，此时回到上一个顶点，对这个顶点未访问过的邻接点进行访问……直到所有的顶点都被访问过。很容易知道，在深度优先遍历中访问的所有顶点都是相互可达或相连的。根据Union-Find算法，我们用一个id标记每个连通分量，即具有相同id的顶点属于同一个连通分量。上面已经分析了连通分量的个数范围是[1,graph.vertexNum]，所以需要的id个数graph.vertexNum就足够了，数组int[]id中存储的id范围是[0,graph.vertexNum–1]。下面是求一个无向图所有连通图的代码，使用的无向图就是上面3个连通图。packageChap7;importjava.util.LinkedList;publicclassCC{//用来标记访问过的顶点，保证每个顶点值访问一次privateboolean[]marked;//为每个连接的组件标记一个idprivateint[]id;//connected组件个数privateintcount;publicCC(UndiGraphgraph){marked=newboolean[graph.vertexNum()];id=newint[graph.vertexNum()];for(ints=0;sgraph,intv){//设置标记为vertexjustaccessed[v]=true;id[v]=count;//从v的所有相邻点中选择一个未访问过的顶点for(intw:graph.adj(v)){if(!marked[w]){dfs(graph,w);}}}publicbooleanconnected(intv,intw){returnid[v]==id[w];}publicintid(intv){returnid[v];}publicintcount(){returncount;}publicstaticvoidmain(String[]args){//edgeint[][]edges={{0,6},{0,2},{0,1},{0,5},{3,4},{3,5},{4,5},{4,6},{7,8},{9,10},{9,11},{9,12},{11,12}};UndiGraphgraph=newUndiGraph<>(13,edges);CCcc=newCC(graph);//M为连通分量数intM=cc.count();System.out.println(M+"连通分量");LinkedList[]components=(LinkedList[])newLinkedList[M];for(inti=0;i();}//将是同一个id的顶点属于同一个链表for(intv=0;vgraph){marked=newboolean[graph.vertexNum()];for(ints=0;sw的路径，也有w->v的路径，那么v和w是强连通的，也说明这是一个环结构。一个有V个顶点的有向图包含[1,V]范围内的多个强连通分量——强连通图只有一个强连通分量，而有向无环图包含V个强连通分量部分。下图包含5个强连通分量。与计算无向图中的连通分量一样，计算有向图中的强连通分量也是深度优先搜索的一种应用。这种称为Kosaraju的算法可以通过简单地在上面的代码中添加几行来实现。虽然这个算法实现起来很简单，但理解起来并不容易。nullzx的博客园的博文很不错。看了之后，明白了Kosaraju算法的神奇方法……上图是一个有向图，有两个强连通分量。强连通分量和强连通分量之间没有环，否则两个连通分量是一个整体，即认为是同一个强连通分量。如果把连通分量缩减为一个顶点，那么上图就是一个有两个顶点的无环图，左边的顶点指向右边的顶点。如果从左边强连通分量中的任意一个顶点开始DFS，只需要一次调用就可以访问图中所有的顶点，主要是因为A2指向两个连通分量之间的B3；相反，从右边的强连通分量开始，从中的任意顶点开始深度优先搜索，需要调用两次DFS——这恰好是强连通分量的个数，以及调用DFS每次访问的顶点都是一个强连通分量中的所有顶点（假设这句话是正确的，下面会给出这个命题的证明），比如第一次调用DFS时，访问了B3、B4、B5，而这些三个顶点刚好构成右边强连通分量的所有顶点。反之，为了找到所有的强连通分量，保证DFS访问顶点的顺序是B强连通分量中的任意一个顶点在A强连通分量的所有顶点之前。或者换个角度想想。将连通分量缩减为顶点后，整个图就变成了无环图。DFS访问顶点的顺序是：先访问那些没有指向任何连通分量（顶点）的顶点，比如上面的A2指向B3，那么应该先访问B中的顶点。更笼统地说，DFS会先访问那些度数为0的连通分量（作为一个顶点），从而保证对DFS的调用必须在同一个连通分量中递归，不会运行到其他连通分量。拿。如果先访问那些指向其他分量（出度不为0）的分量，DFS肯定能进入其他连通分量，比如A连通分量通过A2进入B连通分量。在这种情况下，一个DFS遍历多个强连通分量根本达不到目的。比如B3、A2、A0、A1、B4、B5，按照这个顺序调用DFS可以保证DFS会被调用两次。当然，顺序不是唯一的。DFS中有一个通用的顺序可以保证这种关系，即倒序。所谓逆序就是在DFS递归调用返回之前，将顶点压入栈得到的序列。比如dfs(s)->dfs(v)的递归调用栈，表示一条s->v的路径，v会先于s返回，所以先存到v，再存到s，顺序在堆栈是sv。现在我们可以说说Kosaraju算法的思想：将原图反转。对反转图进行深度优先遍历，得到顶点的倒序。回到原图，按照上面得到的逆序序列的顺序对原图进行深度优先搜索。（而不是按照0,1,2...的顶点顺序）我们来看看为什么反转图的倒序就是我们需要的序列。上图是反转后的有向图。设原图为G，反转图为Gr。深度优先搜索Gr有两种可能：从强连通分量A中的任意一个顶点开始，需要调用两次DFS，第一次将A0、A1、A2压入栈中；第二次将B3、B4、B5压入栈中。在这种情况下，强连通分量B的所有顶点都在强连通分量A之前。从强连通分量B中的任意一个顶点开始，只需调用一个DFS就可以遍历所有顶点。因为是倒序的，因为最后会返回B中第一个访问过的顶点，所以在栈顶。以上两种情况保证B中至少有一个顶点在A中的所有顶点之前，返回原图时，会先对B中的顶点进行DFS。扩展到具有多个强连通分量的有向图，上述推论仍然有效。逆向图的逆向序列实际上是一个伪拓扑序列（“伪”是因为可能存在环结构）。将连通分量化为顶点后，有向图是无环的，逆向图的逆后序成为拓扑序列——入度为0的顶点总是在先。那么在原图中，拓扑序列就变成了出度为0的顶点排在最前面。根据上面的分析，如果对那些出度为0的分量（已经被视为顶点）进行DFS，则可以保证每次DFS访问的顶点都在同一个强连通分量下.为了证明Kosaraju算法的正确性，需要证明这个命题：DFS是按照逆向图的逆序对原图进行的，并且每次DFS中访问的所有顶点都在同一个连通分量中。上面说了这么多，只是定性的解释了为什么用逆向图的逆向序列这样的序列可以达到目的，命题的后半部分……在上面的分析中我们假设它是正确的，实际上这个命题需要严格的证明下面的证明是在命题前半句的前提下证明后半句的正确性。为了证明这个命题，有两点需要证明（在以逆向图的逆序进行DFS的前提下）：在调用dfs(G，小号）;dfs(G,s)到达的任何顶点v必须与s强连接。第一点，用反证的方法：假设在dfs(G,s)的调用中有一个顶点v没有被访问到，因为有一条从s->v的路径，也就是说v已经被在调用dfs(G,s)之前访问。访问过（否则不符合假设）；并且因为还有一条v->s的路径，所以在调用dfs(G,v)之后s肯定会被标记为visited，这样dfs(G,v)就不会被调用s)，这与我们的假设矛盾dfs(G,s)将被调用。所以原命题成立。第二点是dfs(G,s)可以到达顶点v，说明存在s->v的路径。要证明s和v是强连通的，只需要证明还存在一个v->原始图G中的s。该路径相当于在反向图Gr中从s->v找到一条路径。由于深度优先搜索是倒序进行的，所以必须在dfs(Gr,s)之前返回Gr中的dfs(Gr,v)，否则倒序变为[v,s]，原图在dfs时被调用时，dfs(G,v)将首先被调用。这时，如果原图中存在v->s的路径，那么dfs(G,v)调用后，s会被标记为visited，这样dfs(G,s)就不会被调用了——这与我们假设dfs(G,s)将被调用并到达v顶点的假设相矛盾。所以在Gr中，dfs(Gr,v)必须在dfs(Gr,s)之前返回。在dfs(Gr,s)之前调用dfs(Gr,v)有两种情况，在dfs(Gr,s)中也有调用。s)在呼叫结束之前结束。即dfs(Gr,v)调用->dfs(Gr,v)结束->dfs(Gr,s)调用->dfs(Gr,s)在dfs(Gr,s)之后结束dfs(Gr,v)调用)，并在对dfs(Gr,s)的调用结束之前结束。即dfs(Gr,s)call->dfs(Gr,v)call->dfs(Gr,v)end->dfs(Gr,s)end第一种情况是不可能的。第一种情况下的调用是不可能的，因为Gr中有v->s（G中有s->v）。第二种情况只是说明Gr中存在一条s->v的路径。证明！如下图，中图和右图分别对应以上两种情况。证明也证明了，应该给出代码。packageChap7;importjava.util.LinkedList;/***在有向图中寻找强连通分量*/publicclassKosarajuSCC{//用于标记访问过的顶点，保证每个顶点值访问一次privateboolean[]标记;//为每个连通分量标记一个idprivateint[]id;//连通分量的个数privateintcount;publicKosarajuSCC(DiGraphgraph){marked=newboolean[graph.vertexNum()];id=newint[graph.vertexNum()];//将原图G反转得到GrDFSorderorder=newDFSorder(graph.reverse());//dfsfor(ints:order.reversePost()){if(!marked[s])按照Gr的逆序{dfs(graph,s);//dfs调用是连通分量，第一个连接的组件ID为0。//之后分配的id要自增，第二个连通分量的id为1，依次类推count++;}}}privatevoiddfs(DiGraphgraph,intv){//设置标志为thevertexjustvisited[v]=true;id[v]=count;//从v的所有相邻点中选择一个没有被访问过的顶点for(intw:graph.adj(v)){if(!marked[w]){dfs(graph,w);}}}publicbooleanstronglyConnected(intv,intw){returnid[v]==id[w];}publicintid(intv){returnid[v];}publicintcount(){returncount;}publicstaticvoidmain(String[]args){//edgeint[][]edges={{0,1},{0,5},{2,3},{2,0},{3,2},{3,5},{4,2},{4,3},{4,5},{5,4},{6,0},{6,4},{6,9},{7,6},{7,8},{8,9},{8,7},{9,10},{9,11},{10,12},{11,4},{11,12},{12,9}};DiGraphgraph=newDiGraph<>(13,edges);KosarajuSCCcc=newKosarajuSCC(graph);//M为连通分量个数intM=cc.count();System.out.println(M+"connectedcomponents");LinkedList[]components=(LinkedList[])newLinkedList[M];for(inti=0;i();}//将相同id的顶点赋值给同一个链表for(intv=0;v
