一、
求无向的图的关节点的这个算法是我觉得比较难理解的算法之一，我觉得难并不是难在算
法本身，而是难在该算法的递归的实现上，特别是在DFSArticul()递归退出以后才可以进行
low[]函数的计算，这点，如果是在自己独立思考来进行编程的话，可能是很难想出来的，因
为计算low[]函数必须要深度优先生成树建立之后在可以进行求解，即求解的顺序实质是对
DFSTree进行后序遍历，这是其一。其二，该算法的核心思想是求三者中的最小，即dfn函
数，还是有困难的，当初，我自己的想法是先深度优先遍历图，建立相应DFS树，同时记录下
每个顶点的DFS序数，然后再后续遍历这棵树来求解low[]函数，如果是这样的话，时间复杂
度就大多了，下面是我写的代码，这个代码本质上并不是我自己编写的，是参照严蔚敏教材上
的代码写的一个成员函数，但我觉得这个代码写得确实是太精辟了，如果是我自己，是写不出
来的，下面的代码我付上了详细的注释，大家参考，另外代码已经作了一定的改动，因为严蔚
敏教材上的代码仅仅针对邻接表，而我经过修改后也可以针对邻接矩阵,代码已经通过 测试了,
大家参考：
二、求解算法
利用深度优先搜索便可以求的图的关节点，本由此可判别图是否重连通。
从任一点出发深度优先遍历得到优先生成树，对于树中任一顶点Ｖ而言，其孩子节点为邻接点。由深度优先生成树可得出两类关节点的特性：
（１）若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在连接不同子树顶点的边，若删除此节点，则树便成为森林。
（２）若生成树中某个非叶子顶点V，其某棵子树的根和子树中的其他节点均没有指向V的祖先的回边，则V为关节点。因为删去v，则其子树和图的其它部分被分割开来
定义
low[v] 设对连通图G＝（V,E）进行先深搜索的先深编号为dnf[v]，产生的先深生成树为S＝（V,T），B试回退边之集。对每个顶点v，low[v]定义如下
low[v]=Min{dfn[v],Min{low[w]|w是v的一个子女}，Min{dfn[x]|（v，x）是一条回边}}//dfn数组记录顶点的深度优先数
三、///DFSArticul()公有成员函数//递归:从v0出发,通过深度优先遍历当前图,//查找并输出该深度优先生成树上的所有关节点//算法描述概要:定义了dfn[]函数,存放结点的DFS遍历//序数,low[]函数存放通过,当前结点可以/templateint Graphlink::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] min=low[w]; //比v0能达到的更小 if(low[w]>=dfn[v0])//如果子结点u所能到达的顶点的DFS序数还没有v0大 cout< < <<"是一个关节点."<
} else if(dfn[w] min=dfn[w]; //说明w已经在v0之前访问过了是一条回边}low[v0]=min; //得到当前结点v0的low[]函数值return count; //返回当前遍历过的顶点的个数};/DFSArticul()公有成员函数结束///FindArticul()公有成员函数 //调用DFSArticul()函数找出当前图的//所有的关节点,并显示出来,思想：首先判断根结点//是否有多于一个子树,如果是说明根也是关节点，然后//以根的每棵子树根结点为起点继续找关节点/templatevoid Graphlink::FindArticul(){ int n=numVertices; int* dfn=new int[n]; //dfn[]函数的数组 int* low=new int[n]; //low[]函数的数组 for(int i=0;i dfn=1; //以0号顶点为遍历的根结点 int p=getFirstNeighbor(0); //获取根结点0的第一个子结点 int k=DFSArticul(p,dfn,low);//对第一棵子树进行寻找,得到第一棵子树顶点个数 if(k!=n-1) //如果顶点个数不是总顶点数-1 { //怎说明根结点是关节点 cout<<0<<":"< <<"是一个关节点."< p=getNextNeighbor(0,p); //获得子树p的兄弟子树 while(p!=-1) //对其他的子树进行再次的关节点寻找 { if(dfn[p]==0) //如果p还没有被访问过,就从该顶点开始寻找 DFSArticul(p,dfn,low); p=getNextNeighbor(0,p); }; };};FindArticul()函数结束
