扩展或修改强连通算法

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

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

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

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

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

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

(1)扩展或修改强连通算法扩展阅读：

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

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

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

‘贰’ 强连通分量的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;}

‘叁’ 强连通的概念

在计算机图论中,强连通（Strongly Connected）是指有向图G（Directed Graph）中任意两点v1、v2之间都存在着v1到v2的路径(path,若途径的点和边都不重复,则称为路径)及v2到v1的路径。
定理：
一个有向图是强连通的，当且仅当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[u]=Low[u]=++Index // 设定次序编号和Low初值
Stack.push(u) // 将节点u压入栈中
for each (u, v) in E // 枚举每一条边
if (v is not visted) // 如果节点v未被访问过
tarjan(v) // 继续向下找
Low[u] = min(Low[u], Low[v])
else if (v in S) // 如果节点v还在栈内
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
repeat
v = S.pop // 将v退栈，为该强连通分量中一个顶点
print v
until (u== v)
}
接下来是对算法流程的演示。
从节点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已经出栈，不再访问6，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。
继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=4。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。
至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。
可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。
求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是 O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。 在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。 求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。
void tarjan(int i)
{
int j;
DFN[i]=LOW[i]=++Dindex;
instack[i]=true;
Stap[++Stop]=i;
for (edge *e=V[i];e;e=e->next)
{
j=e->t;
if (!DFN[j])
{
tarjan(j);
if (LOW[j]<LOW[i])
LOW[i]=LOW[j];
}
else if (instack[j] && DFN[j]<LOW[i])
LOW[i]=DFN[j];
}
if (DFN[i]==LOW[i])
{
Bcnt++;
do
{
j=Stap[Stop--];
instack[j]=false;
Belong[j]=Bcnt;
}
while (j!=i);
}
}
void solve()
{
int i;
Stop=Bcnt=Dindex=0;
memset(DFN,0,sizeof(DFN));
for (i=1;i<=N;i++)
if (!DFN[i])
tarjan(i);
}

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

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

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

方案2：可以优化1

‘伍’ 如何实现强连通图的优化

暑假 王建德和朱全民跟我们说了,不记得了

‘陆’ 什么叫：强连通 单向连通 弱连通 不连通

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

连通分量：无向图 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的路径中所有的边都必须同向。

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

(6)扩展或修改强连通算法扩展阅读：

强连通图的边问题：

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

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

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

求无向图的连通分量：

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

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

参考资料来源：网络-连通图

‘柒’ 强连通分量的Gabow算法思路

这个算法其实就是Tarjan算法的变异体，我们观察一下，只是它用第二个堆栈来辅助求出强连通分量的根，而不是Tarjan算法里面的indx[]和mlik[]数组。那么，我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。
我们使用类比方法，在Tarjan算法中，每次mlik[i]的修改都是由于环的出现(不然，mlik[i]的值不可能变小)，每次出现环，在这个环里面只剩下一个mlik[i]没有被改变(深度最低的那个)，或者全部被改变，因为那个深度最低的节点在另一个环内。那么Gabow算法中的第二堆栈变化就是删除构成环的节点，只剩深度最低的节点，或者全部删除，这个过程是通过出栈来实现，因为深度最低的那个顶点一定比前面的先访问，那么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问：为什么弹出的都是同一个强连通分量？因为在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢？想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。
现 在，你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现，但是，Gabow算法更精妙，时间更少(不用频繁更新mlik[])。 Gabow_Algorithm:
步骤1:
找一个没有被访问过的节点v，goto step2(v)。否则，算法结束。
步骤2(v):
将v压入堆栈stk1[]和stk2[]
对于v所有的邻接顶点u：
1) 如果没有访问过，则step2(u)
2) 如果访问过，但没有删除，维护stk2[](处理环的过程)
如果stk2[]的顶元素==v，那么输出相应的强连通分量 C++：#include<iostream>usingnamespacestd;constintMAXN=110;typedefintAdjTable[MAXN];//邻接表类型intn;intintm[MAXN];//标记进入顶点时间intbelg[MAXN];//存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量intstk1[MAXN];//辅助堆栈intstk2[MAXN];//辅助堆栈AdjTableadj[MAXN];//邻接表//深搜过程,该算法的主体都在这里voidVisit(intcur,int&sig,int&scc_num){inti;intm[cur]=++sig;stk1[++stk1[0]]=cur;stk2[++stk2[0]]=cur;for(i=1;i<=adj[cur][0];++i){if(0==intm[adj[cur][i]]){Visit(adj[cur][i],sig,scc_num);}elseif(0==belg[adj[cur][i]]){while(intm[stk2[stk2[0]]]>intm[adj[cur][i]]){--stk2[0];}}}if(stk2[stk2[0]]==cur){--stk2[0];++scc_num;do{belg[stk1[stk1[0]]]=scc_num;}while(stk1[stk1[0]--]!=cur);}}//Gabow算法,求解belg[1..n],且返回强连通分量个数,intGabow_StronglyConnectedComponent(){inti,sig,scc_num;memset(belg+1,0,sizeof(int)*n);memset(intm+1,0,sizeof(int)*n);sig=0;scc_num=0;stk1[0]=0;stk2[0]=0;for(i=1;i<=n;++i){if(0==intm[i]){Visit(i,sig,scc_num);}}returnscc_num;}Pascalproceretarjan(r:longint);varx,i,j:longint;begininc(timez);time[r]:=timez;low[r]:=timez;inc(top);zh[top]:=r;fori:=p1[r]top2[r]dobeginj:=e[i].y;iftime[j]=0thentarjan(j);iflow[j]<low[r]thenlow[r]:=low[j];end;iftime[r]=low[r]thenrepeatx:=zh[top];num[x]:=r;low[x]:=n+1;//这句话千万别忘了dec(top);untilx=r;end;

‘捌’ 用C语言和数据结构（只能用这两种）来编写一个判断有向图是否为强连通图的算法

这是一个递归算法：
1、一个节点的图是强连通的，这是递归终止条件
2、G(n)的强连通性变为：图G（n-1）和节点g（n）和G(n-1)的联通问题。
采用递归方式，具体算法要结合你的存储结构实现