关于图论中强连通分量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])
那位大牛能给个解释,
人气:460 ℃ 时间:2020-04-10 11:28:16
解答
这要根据题意而定!
如果光求联通分支,结果是一样的!
你可以画一个简单的图,根据代码,记录每个顶点的DFN和LOW,你会发现他们的区别的!
如果这个题目,你能用tarjan算法,自己想出如何解答,那么你就明白你提出的问题了!
good luck!
推荐
猜你喜欢
- 原子结构图中,最外层电子是8,怎样表示它的离子结构图?
- 工业制氧气一般用压缩空气还是电解水?
- 1.己知定点P(2,0),动点Q在圆x^2+y^2=9上,PQ的垂直平分线交OQ于点M,则动点M的轨迹是?
- 果园里有桃树480棵,比梨树多20%,比苹果树少20%,桔子树比桃树多10%.
- You ___wrong!The moon doesn't ___sun is in the middle___our system
- 竹席味道大是什么原因
- 如图,一个台阶,需铺上地毯,地毯长是多少米?
- 以have开头的是什么疑问句?