2024年10月强连通图是什么（如何判断图是强连通的）

　　⑴强连通图是什么（如何判断图是强连通的

　　⑵如何判断图是强连通的

　　⑶强连通图表明任意两点之间可以互相到达。方案：判断结点A可以到达的点的方法如下：首先SA={A}；while取SA中任意没有被去过的点x，根据以x为起点的有向线段，判断x可以直接到达的点，然后这些点加入SA；如此循环，直到SA中的点的个数没有变化了end这样得到的集合SA是所有A可以到达的点的一个集合。判断SA是否等于S，若不等于S，表明不是强连通。如此循环，求出所有S中的点的能够到达的点集。如果所有的点集都等于S表明强连通图。方案：可以优化

　　⑷连通分量，强连通的定义是什么呢

　　⑸分类:电脑/网络》》程序设计》》其他编程语言解析:你好，介绍连通分量首先要介绍一下连通图。图是由顶点和边组成的，如果从顶点v道顶点v有条路径，则称它们是连通的，如果无向图G中的每两个顶点都是连通的则G就叫做连通图。那么如果任意一个无向图的极大连通子图就叫做连通分量。而如果有向图G中的任意两个顶点都是连通的，那么G就是强连通图。

　　⑹在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径，则称vi和vj是连通的。如果G是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径。图的连通性是图的基本性质。

　　⑺连通图：是指在图论中，连通图基于连通的概念。

　　⑻在一个无向图G中，若从顶点到顶点有路径相连（当然从到也一定有路径，则称和是连通的。如果G是有向图，那么连接和的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。

　　⑼一个无向图G=(V,E)是连通的，那么边的数目大于等于顶点的数目减一：

　　⑽如果G=(V,E)是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：

　　⑾没有回路的无向图是连通的当且仅当它是树，即等价于：

　　⑿强连通和弱连通分别什么意思

　　⒀通路：两点之间有路径即可连通图：任意两点之间存在通路强连通：有向图（前提中，任意两点都有至少一条通路，则此图为强连通图。弱连通图：将有向图的有向边换成无向边得到的图是连通图，则此有向图是弱连通图。

　　⒁n个顶点的强连通图的边数至少有______.(C)什么叫强连通图

　　⒂对于个顶点的强连通图至少有一个边假设n个顶点的强连通图至少有n个边则如果新加一个顶点至少要增加一边在有向图G中,如果对于每一对vi,vj属于G,vi不等于vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图.

　　⒃在计算机图论中,强连通（StronglyConnected是指有向图G（DirectedGraph中任意两点v、v之间都存在着v到v的路径(path,若途径的点和边都不重复,则称为路径)及v到v的路径。定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。证明：充分性如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。必要性如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，Low(u)=Min{DFN(u),Low(v),(u,v)为树枝边，u为v的父节点DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)}当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。算法伪代码如下tarjan(u){DFN=++Index//设定次序编号和Low初值Stack.push(u)//将节点u压入栈中foreach(u,v)inE//枚举每一条边if(visnotvisted)//如果节点v未被访问过tarjan(v)//继续向下找Low)elseif(vinS)//如果节点v还在栈内Low)if(DFN)//如果节点u是强连通分量的根repeatv=S.pop//将v退栈，为该强连通分量中一个顶点printvuntil(u==v)}接下来是对算法流程的演示。从节点开始DFS，把遍历到的节点加入栈中。搜索到节点u=时，DFN，找到了一个强连通分量。退栈到u=v为止，{}为一个强连通分量。返回节点，发现DFN，退栈后{}为一个强连通分量。返回节点，继续搜索到节点，把加入堆栈。发现节点像节点的后向边，节点还在栈中，所以LOW=。继续回到节点，最后访问节点。访问边(,)，还在栈中，所以LOW，把栈中节点全部取出，组成一个连通分量{,,,}。至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{,,,},{},{}。可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。求有向图的强连通分量的Tarjan算法是以其发明者RobertTarjan命名的。RobertTarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。voidtarjan(inti){intj;DFN=++Dindex;instack=true;Stap=i;for(edge*e=V;e;e=e-》next){j=e-》t;if(!DFN){tarjan(j);if(LOW)LOW;}elseif(instack)LOW;}if(DFN){Bt++;do{j=Stap;instack=false;Belong=Bt;}while(j!=i);}}voidsolve(){inti;Stop=Bt=Dindex=;memset(DFN,,sizeof(DFN));for(i=;i《=N;i++)if(!DFN)tarjan(i);}

　　⒄强连通图强分图这两个有啥区别

　　⒅在简单有向图中，若任何两个节点间是相互可达的，则称是强连通图；若任何两个节点之间至少从一个节点到另一个节点是可达的，则称是单向连通图或单侧连通图；若在图中略去边的方向，将它看成无向图后，图是连通的，则称该图是弱连通图。简单有向图中拥有附连通性质的最大子图就是强分图。两个都是连通有向图。(a)是强连通图、单向连通图，亦是弱连通图。任何一对结点之间相互可达。(b)并非任何一对结点相互可达，甚至有几对节点不具有可达性，所以只是弱连通图。

　　⒆什么叫：强连通单向连通弱连通不连通

　　⒇下面是这强连通、单向连通、弱连通、不连通的定义：

　　⒈连通分量：无向图G的一个极大连通子图称为G的一个连通分量（或连通分支。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

　　⒉强连通图：有向图G=(V,E)中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。

　　⒊单向连通图：设G=《V,E》是有向图，如果u-》v意味着图G至多包含一条从u到v的简单路径，则图G为单连通图。

　　⒋弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

　　⒌初级通路：通路中所有的顶点互不相同。初级通路必为简单通路，但反之不真。

　　⒍在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径，则称i和j是连通的。如果G是有向图，那么连接i和j的路径中所有的边都必须同向。

　　⒎如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径。图的连通性是图的基本性质。

　　⒏有n个顶点的强连通图最多有n（n-条边，最少有n条边。

　　⒐最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-/条边，而由于强连通图是有向图，故每条边有两个方向，n（n-/×=n（n-，故有n个顶点的强连通图最多有n（n-条边。

　　⒑最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。

　　⒒求无向图的连通分量：

　　⒓作为遍历图的应用举例，下面我们来讨论如何求图的连通分量。无向图中的极大连通子图称为连通分量。求图的连通分量的目的，是为了确定从图中的一个顶点是否能到达图中的另一个顶点，也就是说，图中任意两个顶点之间是否有路径可达。

　　⒔对于连通图，从图中任一顶点出发遍历图，可以访问到图的所有顶点，即连通图中任意两顶点间都是有路径可达的。

　　⒕参考资料来源：百度百科-连通图

　　⒖强连通图一定是弱连通图那么为什么要分强弱连通图呢

　　⒗我也是初学离散数学，我觉得分强弱连通图和单向连通图是为了所有的有向图都有名字可以区分把，由强连通往下细分会觉得没必要，但是反过来从所有图往上分的话，命名可能就是必要的了。强连通图的定义是针对有向图，而连通图的定义是对无向图。欢迎讨论，有错误的话还望指正