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

问题描述

问 题

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

解决方案

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

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

这篇关于数据结构和算法分析中割点问题.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！