Robert E Tarjan是一个神人。

关于Tarjan求强连通分量的Blog一抓一大把,这里就推荐几篇吧:

#1   #2  #3 

看了这三篇我感觉差不多理解了。

然而还有一些问题

 

1.关于出栈怎么写

 

if (dfn[u]==low[u])
	{
		counter++;
		do
		{
			cache2=stack[head];
			cout<<cache2<<endl;
			head--;
			numbers[cache2]=counter;
			init[cache2]=false;
		} while (cache2!=u);
	}

反正我是这么写的。

 

 

2.关于 Case 2 (牵扯Low定义的问题) 为什么不能改为  

else if(instack[v]==true) low[u]=min(low[u],dfn[v]);

可以看一下StackOverFlow ,和 POJ的 One Way Traffic这道题

StackOF上面给了一个证明,这里引述一下。

 

In tarjan’s dfs search getting lowlink(u):

lowu=min(low, low) (v isn’t visited)

or

lowu=min(low, dfn) (v is still in the stack)

My question is, is it still ok to replace dfnv for lowv in the second case? I know this is incorrect, but I failed finding a counter-example. Could anyone help explain this?

 

 

It’s correct, actually.

The proof of correctness depends on two properties of low. The first is that, for all v, there exists w reachable from v such that dfn<= lowv <= dfnv. The second is that, when determining whether v is a root, we have for all w reachable from v that low<= dfnw.

We can prove inductively that the first property still holds by the fact that, if there’s a path from u to v and a path from v to w, then there’s a path from u to w. As for the second, let low be the original array and low’ be yours. It’s not hard to show that, for all v, at all times, low’v <= lowv, so at the critical moment for v, for all w reachable from v, it holds that low’<= low<= dfnw.

I imagine that the algorithm is presented the way it is to avoid the need to consider intermediate values of low.

 

tarjan算法中low的标准定义是low= min ( dfnu , lowv , dfnw );

 

3.

有任何问题及时补充

欢迎评论来分享您的看法


发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.