求无向的图的关节点的这个算法是我觉得比较难理解的算法之一，
我觉得难并不是难在算法本身，而是难在该算法的递归的实现上，
特别是在DFSArticul()递归退出以后才可以进行low[]函数的计算，
这点，如果是在自己独立思考来进行编程的话，可能是很难想出来
的，因为计算low[]函数必须要深度优先生成树建立之后在可以进
行求解，即求解的顺序实质是对DFSTree进行后序遍历，这是其一。
其二，该算法的核心思想是求三者中的最小，
即dfn[i]，i的所有子孙结点能通过回边达到的最小DFS顶点的序数，
i本身通过回边可以到达的最小DFS顶点序数，这三者之间的最小，其
是说到这里该算法也不难理解，可是关键难就难在怎么编写实现呢？
要一边遍历，一边求low[]函数，还是有困难的，当初，我自己的想法
是先深度优先遍历图，建立相应DFS树，同时记录下每个顶点的DFS序数，
然后再后续遍历这棵树来求解low[]函数，如果是这样的话，时间复杂度
就大多了，下面是我写的代码，这个代码本质上并不是我自己编写的，
是参照严蔚敏教材上的代码写的一个成员函数，但我觉得这个代码写得
确实是太精辟了，如果是我自己，是写不出来的，下面的代码我付上了
详细的注释，大家参考，另外代码已经作了一定的改动，因为严蔚敏教
材上的代码仅仅针对邻接表，而我经过修改后也可以针对邻接矩阵,代码
已经通过 测试了,大家参考：

说实话，这个算法确实是越嚼越有味道...

/////////////////////////////////////////////////
//DFSArticul()公有成员函数
//递归:从v0出发,通过深度优先遍历当前图,
//查找并输出该深度优先生成树上的所有关节点
//算法描述概要:定义了dfn[]函数,存放结点的DFS遍历
//序数,low[]函数存放通过,当前结点可以
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::DFSArticul(int v0,int* dfn,int* low)
{
    static int count=0;        //得到DFS序数的计数器
    count++;                  
    int min=count;             //当前访问的结点v0的DFS序数
    dfn[v0]=count;             //得到当前访问顶点的DFS序数
    for(int ptr=getFirstNeighbor(v0)  
        ;ptr!=-1               //遍历结点v0所有的邻接结点
        ;ptr=getNextNeighbor(v0,ptr))
    {
        int w=ptr;             //w是v0的邻接结点,w也是v0的子结点
        if(dfn[w]==0)          //如果v0的子结点w没有被访问过
        {
            DFSArticul(        //递归:对以w为开始顶点的子图进行递归求关节点
                w,dfn,low);
            if(low[w]<min)     //退出递归以后,如果子结点u能达到的顶点DFS序数比
                min=low[w];    //比v0能达到的更小
            if(low[w]>=dfn[v0])//如果子结点u所能到达的顶点的DFS序数还没有v0大
                cout<<v0<<":"  //说明v0就是一个关节点
                <<getValue(v0)
                <<"是一个关节点."<<endl;
        }
        else if(dfn[w]<min)    //如果w的DFS序数比当前v0的最小回边系数更小
            min=dfn[w];        //说明w已经在v0之前访问过了<v0,w>是一条回边
    }
    low[v0]=min;               //得到当前结点v0的low[]函数值
    return count;              //返回当前遍历过的顶点的个数
};
/////////////////////DFSArticul()公有成员函数结束

/////////////////////////////////////////////////
//FindArticul()公有成员函数
//调用DFSArticul()函数找出当前图的
//所有的关节点,并显示出来,思想：首先判断根结点
//是否有多于一个子树,如果是说明根也是关节点，然后
//以根的每棵子树根结点为起点继续找关节点
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::FindArticul()
{
    int n=numVertices;
    int* dfn=new int[n];        //dfn[]函数的数组
    int* low=new int[n];        //low[]函数的数组
    for(int i=0;i<n;i++)        //初始化dfn[]函数
        dfn[i]=0;
    dfn[0]=1;                   //以0号顶点为遍历的根结点
    int p=getFirstNeighbor(0);  //获取根结点0的第一个子结点
    int k=DFSArticul(p,dfn,low);//对第一棵子树进行寻找,得到第一棵子树顶点个数
    if(k!=n-1)                  //如果顶点个数不是总顶点数-1
    {                           //怎说明根结点是关节点
        cout<<0<<":"<<getValue(0)
            <<"是一个关节点."<<endl;
        p=getNextNeighbor(0,p); //获得子树p的兄弟子树
        while(p!=-1)            //对其他的子树进行再次的关节点寻找
        {
            if(dfn[p]==0)       //如果p还没有被访问过,就从该顶点开始寻找
                DFSArticul(p,dfn,low);
            p=getNextNeighbor(0,p);
        };
    };
};
////////////////////////////FindArticul()函数结束

[[it] 本帖最后由 geninsf009 于 2008-12-7 11:19 编辑 [/it]]