第七章图图例抽象数据类型图的定义图是由一个顶点集V和一个弧集VR构成的数据结构。Graph=(V,VR)其中，VR＝{<v,w>|v,w∈V且P(v,w)}<v,w>表示从v到w的一条弧，并称v为弧尾，w为弧头。P(v,w)定义了弧<v,w>的意义或信息。由于“弧”是有方向的，则称由顶点集和弧集构成的图为有向图。若<v,w>VR必有<w,v>VR,则称(v,w)为顶点v和顶点w之间存在一条边。名词和术语A假设图中有n个顶点，e条边，则假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，顶点的出度:以顶点v为弧尾的弧的数目；设图G=(V,VR)中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图；若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。A结构的建立和销毁CreatGraph(&G,V,VR)://按定义(V,VR)构造图对顶点的访问操作对邻接点的操作插入或删除顶点插入和删除弧遍历图的存储表示Aij={有向图的邻接矩阵为非对称矩阵typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型//对无权图，用1或0表示相邻与否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义VertexType//顶点信息vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph;0A141B0452C353D254E015F123有向图的邻接表AtypedefstructArcNode{intadjvex;//该弧的狐头或狐尾的顶点所在的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//图的种类标志}ALGraph;三、有向图的十字链表存储表示弧的结点结构顶点的结点结构typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;标记边顶点i边顶点j边的相关信息typedefstructEbox{VisitIfmark;//访问标记intivex,jvex;//该边依附的两个顶点的位置structEBox*ilink,*jlink;InfoType*info;//该边信息指针}EBox;typedefstruct{//邻接多重表VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;}AMLGraph;图的遍历从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。V从上页的图解可见:gvoidDFS(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w//递归调用DFS}//DFS首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。voidDFSTraverse(GraphG,Status(*Visit)(intv)){//对图G作深度优先遍历。VisitFunc=Vis