数据结构和算法分析中割点问题.

Question

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

Answer 1

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

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