数据结构教学笔记第七章图

ADTGraph数据关系R： VR＝{<v,w>|v,w∈V基本操作P：DestroyGraph(&G);//销毁图G。GetVex(G,v);vPutVex(&G,v,value);vvalue。NextAdjVex(G,v,w);v（w）wvInsertVex(&G,v);Gv。弧<w,v><w,v>BFSTraverse(G,v,Visit());vG图的表#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20typedefenum{DG,DN,AG,AN}GraphKind;typedefstructArcCell{VRTypeadj;VRTypeInfoType*info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;int um;GraphKindkind;}#defineMAX_VERTEX_NUM20typedefstruct ode{intadjvex; ode*nextarc;InfoType*info; typedefstructVNodeVertexTypedata;ode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListint um;intkind;}#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvexstructArcBox*hlink,InfoType*info;}typedefstructVexNode{VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];int um;}#defineMAX_VERTEX_NUMtypedefemnu{unvisited,visited}VisitIf;typedefstructEbox{VisitIfmark;//标intivex,jvex;structEBox*ilink,*jlink;InfoType*info;}typedefstructVexBox{VertexTypedata;EBox*firstedge;}VexBox;typedefstruct{VexBoxintvexnum,edgenum;}述过程，直至图中所有顶点都到为止。 下列算法使的全局变 Booleanvisited[MAX];//标志数组Status*VisitFunc)(intv);//voidDFSTrverse(GrahG,Status(Visit)(intv)) G作深 for(v=0;v<G.vexnum;visited[v]=FALSE;//标志数组初始for(v=0;v<G.vexnum;if(!visited[v])DFS(G,v);//对尚未的顶点调用}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递归调用}中所有和V0有路径相通的顶点都被到。若此时图中尚有顶点未被,则另voidBFSTraverse(GrphG,Statu(*iit)(intv))for(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(QQfor(v=0;v<G.vexnum;++v)ifvisited[vv尚未EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Qu);uvisited[u]=TRUE;Visit(u);//ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w])EnQueue(Q,w);//u的尚未的邻接顶点 }}//BFSTraver遍历应用举例求一条从 i到顶点s的简单路 Searchintv,ints,char{//vvsPATH中visited[v]=TRUE;//第v个顶点Append(PATH,getVertex(v));//vPATH上forw=FirstAdjVex(v)w!=0&&!found;w=NextAdjVex(v))if(w=s){found=TRUE;AppedPATH,w);elseif(!visited[w])DFSearch(w,//对的尚的邻接顶点w递归调用iffoundDeetePATH);//}求两个顶点之间的一条路径长度最短.将链队列的结点改为“双链”结点，即 中包含next和pro两出队列的结点，即当前的队头指针所指结点链队列的状态如下所示typedefDuLnkListQueuePtr;v I //Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front->next=Q.rear->next=NULL}voidEnQueue(LinkQueue&Q,QelemTypee)//prioup=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;p->priou=Q.rear->next=p;Q.rear=}voidDeQueueLin Q,QelemType&e)//Q.front=Q.front->net;e=Q.front-}条（不构成回路），使“权值之和”为最。vww之间的边中取值最小。nU包含已落在生成树上的点）V-U（未落在生成树的顶点），则在所连UV-U记 点U到V－U的代价最 的 trctVertexTyeVRType}kLocateVexG,uufor(j=0;j<G.vexnum;++j)//辅助数组初始化if(j!=k)closedge[j]u,G.arcs[k][j].adjclosedge[k].lowcost=0;//初始，U＝{u}for(i=0;i<G.vexnum;++i)kminimum(closedge);Tprintf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost0;kUfor(j=0;j<G.vexnum;if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj};}算法二：（算法此重复，直至加上n-1条边为止。ST=(V,{k=i=0;while(k<n-1)若(u,v)加入ST后不使ST中产生回路，则输出边(u,v);且}p=G.vertices[0].firstarc;v=p-if(countG.vexnum)printf(0,G.vertices[0].data);low(v)=Min{visited[v],low[w],visited[k]v为关节点visited[v0]=min=++count;//count计顶点次for(p=G.vertices[v0].firstarc;p;p=p-w=p->adjvex;//wv0if(visited[w]0)wDFSArticul(G,w);low[w]if(low[w]<min)min=low[w];if(low[w]>=visited[v0])printf(v0,if(visited[w]<min)min=}low[v0]=弧中查找权值最者;长度次短的路径可能有两种情况是从源点直接到该点的路径 ，源点到a, 到Dis[k]表示当前所求得的从源点k的最短路径Dist[k]=<源点到顶点 弧上的权值或者k弧上的权值>v到v的 //若<vi,v1>,<v1,vj>存在，则存在路径{vi,//路径中所含顶点序号不大则存在条路径 ,v2,//⋯vivj的问假设以有向图表一个工程的施工图或程序数据流图，则图中不允许出现回限定次序关系的顶点，则可人为加上任意的次序关系。一、从有向中选取一个没有前驱的顶点，并输出之;while(v<>0){printf(v);++m;while(w<>0)}}ifm<nprintf“(顶点)”的最