关于图论中强连通分量tarjan算法的问题
问题描述：
关于图论中强连通分量tarjan算法的问题
对于其中的一部分
for each (u,v) in E // 枚举每一条边
if (v is not visted) // 如果节点v未被访问过
then tarjan(v) // 继续向下找
Low[u] = min(Low[u],Low[v])
else if (v in S) // 如果节点v还在栈内
\x05Low[u] = min(Low[u],DFN[v])
其中后部分为什么是Low[u] = min(Low[u],DFN[v])而不是Low[u] = min(Low[u],Low[v])
那位大牛能给个解释,
答
这要根据题意而定!
如果光求联通分支,结果是一样的!
你可以画一个简单的图,根据代码,记录每个顶点的DFN和LOW,你会发现他们的区别的!
如果这个题目,你能用tarjan算法,自己想出如何解答,那么你就明白你提出的问题了!
good luck!