强连通图算法

❶ 中国邮递员问题 强连通图 如何找最优解

是离散数学中图论的一题，由中国组合数学家管梅谷教授提出。
题目：邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？
如果你有学过离散数学，那请看下面的解
首先，这不是一个NPC问题，即存在多项式复杂度的算法
算法过程：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。

❷ 请问数据结构中图的强连通分量是什么能具体解释一下吗

强连通分量是有向图中的概念，就是每一个顶点到其它点都由路径，注意有方向。

step1：对原图G进行深度优先遍历，记录每个节点的离开时间。

step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。

step3：如果还有顶点没有删除，继续step2，否则算法结束。

如果把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

(2)强连通图算法扩展阅读：

Kosaraju算法的第二次深搜隐藏了一个拓扑性质，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它们不具有拓扑性质。

Tarjan算法用堆栈和标记，Gabow用两个堆栈（其中一个堆栈的实质是代替了Tarjan算法的标记部分）来代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法要高。

在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢？想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

❸ 强连通分量(Kosaraju算法)

{ //判断各个强连通分量是否为出度为0的分量 for(int t = 0; t

❹ [图论]DFS求有向图强连通分量算法的正确性

详情请见《数据结构》第三版

❺ 请问如何求(有向/无向)图的强连通分量，还有，基础一点，怎么求有几个连通图啊

寻找强烈连接组件的算法有Tarjan的，kosaraju两种算法
相比Tarjan的写了相对简单Kosaraju的太麻烦了

但认为它是相对简单

Kosaraju其他要求强烈连接组件如果有，估计需要更先进的数据结构算法的算法

建议或学校根据Tarjan的，因为他可以帮助你做很多事情，如寻求桥切点减少环，但也写一些简单的 BR p>连通图的方法可以直接DFS每个DFS一个点把它记录已经达到了，然后继续向下搜索，每次DFS可以计算出一个连通图

附加Tarjan的代码</ VAR

下，头，点：数组[1 .. 1000] Longint型;

时间，TOT，I，J，N，M，X，Y，T：Longint型;

V：ARRAY [1 .. 10000]字节;

F，Z，Q：ARRAY [1 .. 1000] Longint型;

低，原因：[1阵列。 0.10000] Longint型;

函数min（X，Y：Longint型）：Longint型;

开始

如果x <y，那么退出（X）其他出口（Y）;

结束;

程序地址（X，Y：Longint型）;

开始

公司（TOT）;

下一个[合计]：=头[X]

头[X]：= TOT

点[合计]：= Y;

结束;

程序DFS（X：Longint型）;

VAR

I，J： Longint型;

公司（时间）开始;

低[X]：=时间;

原因[X]：=时间;

V [X]：= 1

公司（T）;

Z [T]：= X;

：=头[X]

而J > 0

开始

V [点[J] = 0，那么（DFS点[J]）;

如果v [点[J] <2低[X]：= MIN（下限[点[ J]，低[X]）;

J：=未来[J];

结束;

低[X] =原因[X]，然后

开始...... / a>公司（TOT）;

而Z [T +1] > X你

开始

公司（Q [合计]）;

F [Z [T]] ：= TOT

V [Z [T]]：= 2;

十二月（T）;

结束;

结束;

结束;

开始

我：= 1米做
开始

readln（X，Y）;

加载（，Y readln（N，M））

结束;

TOT：= 0;时间：= 0;

我：= 1到n做

V [I] = 0，则DFS（I）;

/ / writeln（TOT）;

我：= 1到n做

如果q [F [I]]> 1，则writeln（'T'）其他writeln（'F '）;
结束。

❻ 强连通分量的Kosaraju算法思路

这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。步骤1：先用对原图G进行深搜形成森林(树)，步骤2：然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林，继续步骤2直到
没有顶点为止。
改进思路：
当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于GT来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。
隐藏性质:
分析到这里，我们已经知道怎么求强连通分量了。但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。
Kosaraju_Algorithm:
step1：对原图G进行深度优先遍历，记录每个节点的离开时间。
step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。
step3：如果还有顶点没有删除，继续step2，否则算法结束。
C++
#include
#include
using namespace std;const int MAXN=110;int n;bool flag[MAXN];//访问标志数组int belg[MAXN];//存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[MAXN];//结束时间标记,其中numb[i]表示离开时间为i的顶点AdjTableadj[MAXN],radj[MAXN];//邻接表,逆邻接表//用于第一次深搜,求得numb[1..n]的值voidVisitOne(intcur,int&sig){flag[cur]=true;for(inti=1;i<=adj[cur][0];++i){if(false==flag[adj[cur][i]]){VisitOne(adj[cur][i],sig);}}numb[++sig]=cur;}//用于第二次深搜,求得belg[1..n]的值voidVisitTwo(intcur,intsig){flag[cur]=true;belg[cur]=sig;for(inti=1;i<=radj[cur][0];++i){if(false==flag[radj[cur][i]]){VisitTwo(radj[cur][i],sig);}}}//Kosaraju算法,返回为强连通分量个数intKosaraju_StronglyConnectedComponent(){inti,sig;//第一次深搜memset(flag+1,0,sizeof(bool)*n);for(sig=0,i=1;i<=n;++i){if(false==flag[i]){VisitOne(i,sig);}}//第二次深搜memset(flag+1,0,sizeof(bool)*n);for(sig=0,i=n;i>0;--i){if(false==flag[numb[i]]){VisitTwo(numb[i],++sig);}}returnsig;}

❼ 怎么用c语言和数据结构来编写一个判断有向图是否为强连通图的算法

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

如此循环，求出所有S中的点的能够到达的点集。如果所有的点集都等于S表明强连通图。

方案2：可以优化1