数据结构和算法分析中割点问题. 财富值70

2017-01-21 17:52发布

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中判断就一直成立,每个都是割点啊、还有就是后面的那个特殊情况没有理解。请大家帮忙讲解一下。谢谢!

友情提示: 此问题已得到解决,问题已经关闭,关闭后问题禁止继续编辑,回答。
该问题目前已经被作者或者管理员关闭, 无法添加新回复
2条回答

if(Low[W] >= Num[V])只有在树的情况下成立,而树的每个节点都是割点,失去任一个节点都会导致不连通。如果Low[W] >= Num[V]不成立,那么就是WV之前的某节点也有边相连,成环,而去掉环上任一节点不会导致不连通。

形象上的,每个割点分隔了两个或者更多的点集,这两部分点集除了割点外是不连通的。AssignNUm将点集按树的层次划分,AssignLow则是将把连通的点集攒聚在一起。最终如果某点分割的两边点集不连通,即Low[W] >= Num[V],从W追溯到的最高层次的点不大于Num[V],则此点为割点。

一周热门 更多>