Tarjan算法求解HOJ1007

《Tarjan算法求解HOJ1007》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Tarjan算法求解HOJ1007之前就写过Tarjan算法，但是用来求解有向图强连通分量。这次用来求关节点还用和以前一样的思路，发现好像不行。接下来分别说说用tarjan算法求解有向图强连通分量和无向图关节点。一、tarjan算法求解有向图强连通分量如果在有向图中两个顶点可以互相达到，称这两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的强连通子图，称为强连通分量。比如下面这个图：531642子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。求解强连通分量的方法大致是：dfs整个图，则会生成一棵

2、树，按照深度优先搜索的顺序给每个节点定义一个order，再定义一个low，low代表该节点在该生成树上面往上最远可以到达的节点，初始化为order。每遍历一个节点，将其压入栈中。求解强连通分量关键在于找圈。一个强连通图可以找到一个大圈，一个非强连通图可以找到几个圈。例如生成一个树：43211->2->3->1为一个圈，则代表{1,2,3}构成一个强连通分量，结点3的low值为1代表它可以向上指向节点1。对于任意节点A，它的low值可能大于它儿子S的low值，但是节点A可以到达节点S，因此也可以到达S的low值指向的节点。因此low[A]=min(low[A]，low[S]).当一个节点P的所有

3、儿子都已遍历完，它的low值还等于order值，说明它无法到达它上面的节点，也就说明包含它的圈已经达到最大，弹出栈中节点直至栈顶节点的low与order相等，此时栈顶节点即为P，再弹出P，P所在的强连通分量即全部弹出。继续dfs,找出其他的强连通分量。代码：voidtarjan(graph&G,node&v){low[v.position]=dfn[v.position]=tot;tot++;S.push(v);flag[v.position]=true;edgePtrpointer=v.firstEdge;for(;pointer!=NULL;pointer=pointer->next){n

4、odew=G.points[pointer->position];if(dfn[pointer->position]==0){tarjan(G,G.points[pointer->position]);low[v.position]=min(low[v.position],low[w.position]);}elseif(flag[w.position])low[v.position]=min(low[v.position],low[w.position]);}if(low[v.position]==dfn[v.position]){cout<<"第"<

5、hile(low[S.top().position]!=dfn[S.top().position]){cout<<"v"<

6、码：elseif(flag[w.position])low[v.position]=min(low[v.position],low[w.position]);那么就会将已弹出节点弄到现在要找的强连通分量。而已弹出节点不应该再出现，不应该再进行任何操作。第一个条件是dfn[pointer->position]==0，第二个条件flag[w.position].对于已弹出节点不满足任何一个条件，因此不进行任何操作。已弹出节点不应该再出现，这是因为一个节点既然已经被弹出，就说明它在一个强连通分量上，那么它就不可能再出现在另一个强连通分量上，因此在判断新的连通分量时不必考虑它.若它又出现在另一个强连通

7、分量上，那么说明它在两个圈上，如下所示：但是这两个圈（或者说是环套环）可以构成一个更大的圈，也就是说这两个强连通分量会构成一个更大的强连通分量。输出时会把这个更大的强连通分量输出，因此也就不存在一个节点在两个强连通分量上。二、tarjan算法求解无向图关节点对于无向图求解关节点，对于关节点A，它肯定存在某个儿子B的low大于等于A的order值，因此删去A后，B将与A以上的节点失去联系，因此A是关