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

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]，则此点为割点。