说说编写求无向图的关节点算法的程序的一点体会。
求无向的图的关节点的这个算法是我觉得比较难理解的算法之一，我觉得难并不是难在算法本身，而是难在该算法的递归的实现上，
特别是在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]]
