void AssignNum(vertex V) { vertex M; Num[V] = counter++; Visitied[V] = True; for each W adjanct to V if(!Visited[W]) { Parent[W] = V; AssignNum[W]; } } void AssignLow(vertex V) { vertex W; Low[V] = Num[V]; for each W adjanct to V { if(Num[W]>Num[V]) { AssignLow(W); if(Low[W]>=Num[V])//这里不就一直成立,每个点都是割点 printf("V is an articulation point"); Low[V] = Min(Low[V],Low[W]); } else if(Parent[V]!=W)//V怎么会临接到W呢? Low[V] = Min(Low[V],Nun[W]); } }
数据结构书上将割点的部分,变量的意义在图上。我不明白的是:assignlow中每个Low(W)=Num(W);而Num(W)是递增的,那么assignlow中判断就一直成立,每个都是割点啊、还有就是后面的那个特殊情况没有理解。请大家帮忙讲解一下。谢谢!
付费偷看金额在0.1-10元之间
if(Low[W] >= Num[V])
只有在树的情况下成立,而树的每个节点都是割点,失去任一个节点都会导致不连通。如果Low[W] >= Num[V]
不成立,那么就是W
和V
之前的某节点也有边相连,成环,而去掉环上任一节点不会导致不连通。形象上的,每个割点分隔了两个或者更多的点集,这两部分点集除了割点外是不连通的。
AssignNUm
将点集按树的层次划分,AssignLow
则是将把连通的点集攒聚在一起。最终如果某点分割的两边点集不连通,即Low[W] >= Num[V]
,从W
追溯到的最高层次的点不大于Num[V]
,则此点为割点。一周热门 更多>