关节点

第七章图7.1抽象数据类型图的定义ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R＝{VR}VR＝{v,w|v,w∈V且P(v,w)，v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}名词和术语有向图、无向图、网、子图弧头、弧尾、边完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、回路简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林、最小生成树基本操作P：结构的建立和销毁:CreateGraph(&G,V,VR);//按V和VR的定义构造图G。DestroyGraph(&G);//销毁图G。对顶点的访问操作:LocateVex(G,u);//若G中存在顶点u，则返回该顶点//在图中位置；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作:FirstAdjVex(G,v);//返回v的第一个邻接点。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）下一个//邻接点。若w是v的最后一个邻//接点，则返回“空”。插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧v,w，若G是无//向的，则还增添对称弧w,v。DeleteArc(&G,v,w);//在G中删除弧v,w，若G是无//向的，则还删除对称弧w,v。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图//G，并对每个顶点调用函数//Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图//G，并对每个顶点调用函数//Visit一次且仅一次。7.2图的存储表示图的数组(邻接矩阵)存储表示#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,AG,AN}GraphKind;//{有向图,有向网,无向图,无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧(边)数GraphKindkind;//图的种类标志}MGraph;1.图的邻接表存储表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;1.有向图的十字链表存储表示#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;//该弧的尾和头顶点的位置structArcBox*hlink,*tlink;//分别指向下一个弧头相同和弧尾相同的弧的指针域InfoType*info;//该弧相关信息的指针}ArcBox;typedefstructVexNode{VertexTypedata;ArcBox*firstin,*firstout;//分别指向该顶点第一条入弧和出弧}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表头向量intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;1.无向图的邻接多重表存储表示#defineMAX_VERTEX_NUM20typedefemnu{unvisited,visited}VisitIf;typedefstructEbox{VisitIfmark;//访问标记intivex,jvex;//该边依附的两个顶点的位置structEBox*ilink,*jlink;//分别指向依附这两个顶点的下一条边InfoType*info;//该边信息指针}EBox;typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;typedefstruct{VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;//无向图的当前顶点数和边数}AMLGraph;7.3图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。一、深度优先搜索从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。//---下列算法使用的全局变量---Booleanvisited[MAX];//访问标志数组Status(*VisitFunc)(intv);//函数变量voidDFSTraverse(GraphG,Status(*Visit)(intv)){//对图G作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}voidDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图G。visited[v]=TRUE;VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS}二、广度优先搜索从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。voidBFSTraverse(GraphG,Status(*Visit)(intv)){//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。for(v=0;vG.vexnum;++v)visited[v]=FALSE;InitQueue(Q);//置空的辅助队列Qfor(v=0;vG.vexnum;++v)if(!visited[v]){//v尚未访问EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为uvisited[u]=TRUE;Visit(u);//访问ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w])EnQueue(Q,w);//u的尚未访问的邻接顶点w入队列Q7.4最小生成树问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。算法一：（普里姆算法）可取图中任意一个顶点v作为生成树的根，之后若要往生成树上添加顶点w，则在顶点v和顶点w之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。记录从顶点集U到V－U的代价最小的边的辅助数组：struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];k=LocateVex(G,u);//顶点u为构造生成树的起始点for(j=0;jG.vexnum;++j)//辅助数组初始化if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;//初始，U＝{u}for(i=0;iG.vexnum;++i){//在其余顶点中选择k=minimum(closedge);//求出T的下一个结点(k)printf(closedge[k].adjvex,G.vexs[k]);//输出生成树的边closedge[k].lowcost=0;//第k顶点并入U集for(j=0;jG.vexnum;++j)if(G.arcs[k][j].adjclosedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};//新顶点并入U后重新选择最小边}算法二：（克鲁斯卡尔算法）为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。算法:构造非连通图ST=(V,{});k=i=0;while(kn-1){++i;从边集E中选取第i条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则输出边(u,v);且k++;}一般来讲，由于普里姆算法的时间复杂度为O(n2)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。7.5重（双）连通图和关节点问题：若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。图的双连通性对于表示通讯或运输的图来说，有着重要的意义。若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。显然，没有关节点的连通图为双连通图。关节点的特征：假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。·若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点;·对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。如何判别？1)设V0为深度优先遍历的出发点p=G.vertices[0].firstarc;v=p-adjvex;DFSArticul(G,v);//从第v顶点出发深度优先搜索if(count