育才学习网强连通分量怎么写
1.请问数据结构中图的强连通分量是什么
有向图的极大强连通子图，称为强连通分量（strongly connected components）。
在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通（strongly connected）。如果有向图G的每两个顶点都强连通，称G是一个强连通图。
扩展资料：
强连通分量Tarjan算法
任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。
维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值（mlik[i]初始化为indx[i]）。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根。
因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。
至于拿出强连通分量，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的（剩下节点）子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。
这样，由于当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。
可以用反证法证明这个做法的正确性。假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。
参考资料来源：百度百科-强连通分量
2.强连通分量的Tarjan算法思路
这个算法思路不难理解，由开篇第一句话可知，任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么其实，我们只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。
那么如何确定强连通分量的根，在这里我们维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值（mlik[i]初始化为indx[i]）。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根，为什么呢？因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。
至于如何拿出强连通分量，这个其实很简单，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的（剩下节点）子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。现 在知道如何拿出了强连通分量了吧？是的，因为当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗？假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。现 在没有疑问了吧，那么算法介绍就完了。
3.请问如何求（有向/无向）图的强连通分量,还有,基础一点,怎么求有
求强连通分量的算法有tarjan和kosaraju 两种算法
相较之下 tarjan写起来比较简单 Kosaraju比较麻烦
但是想起来 Kosaraju比较简单
其他求强连通分量的算法 要是还有的话 估计就是需要更高深的数据结构的算法了
建议还是学下tarjan 因为他可以帮你做很多事 比如 求桥 求割点 缩环 而且写起来也很简单
连通图的求法可以直接DFS 每次DFS到一个点 就把它记录成已到达 然后继续向下搜索 每次DFS就可以求出一个连通图
附上tarjan的代码
var
next,head,point:array[1..1000] of longint;
time,tot,i,j,n,m,x,y,t:longint;
v:array[1..10000] of byte;
f,z,q:array[1..1000] of longint;
low,rea:array[1..10000] of longint;
function min(x,y:longint):longint;
begin
if xend;
procedure add(x,y:longint);
begin
inc(tot);
next[tot]:=head[x];
head[x]:=tot;
point[tot]:=y;
end;
procedure dfs(x:Longint);
var
i,j:longint;
begin
inc(time);
low[x]:=time;
rea[x]:=time;
v[x]:=1;
inc(t);
z[t]:=x;
j:=head[x];
while j0 do
begin
if v[point[j]]=0 then dfs(point[j]);
if v[point[j]]j:=next[j];
end;
if low[x]=rea[x] then
begin
inc(tot);
while z[t+1]x do
begin
inc(q[tot]);
f[z[t]]:=tot;
v[z[t]]:=2;
dec(t);
end;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
add(x,y);
end;
tot:=0; time:=0;
for i:=1 to n do
if v[i]=0 then dfs(i);
//writeln(tot);
for i:=1 to n do
if q[f[i]]1 then writeln('T') else writeln('F');
end.
转载请注明出处育才学习网 » 图的强连通分量