第7章_图+.

7.1抽象数据类型图的定义7.2图的存储表示7.3图的遍历7.4最小生成树7.5重（双）连通图和关节点7.6两点之间的最短路径问题7.7拓扑排序7.8关键路径第七章图图是由一个顶点集V和一个弧集R构成的数据结构。Graph=(V,VR)其中，VR＝{v,w|v,w∈V且P(v,w)}v,w表示从v到w的一条弧，并称w为弧头，v为弧尾。谓词P(v,w)定义了弧v,w的意义或信息。图的结构定义:7.1抽象数据类型图的定义数据对象V：顶点集V。数据关系R：R={VR}VR＝{v,w|v,w∈V且P(v,w)}基本操作P：{13种6类：创建销毁、顶点访问、顶点的插入删除、弧的插入删除邻接点的访问、遍历}}ADTGraph；ADTGraph{7.1抽象数据类型图的定义有向完全图—n个顶点的有向图最大边数是n(n-1)无向完全图—n个顶点的无向图最大边数是n(n-1)/2权—与图的边或弧相关的数叫权网—带权的图叫网子图—如果图G(V,E)和图G’(V’,E’),满足：•V’V•E’E则称G’为G的子图顶点的度•无向图中，顶点的度为与每个顶点相连的边数•有向图中，顶点的度分成入度与出度–入度：以该顶点为头的弧的数目–出度：以该顶点为尾的弧的数目路径—路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或Vij-1,VijVR,(1jn)路径长度——沿路径边的数目或沿路径各边权值之和回路——第一个顶点和最后一个顶点相同的路径简单路径——序列中顶点不重复出现的路径简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路连通——从顶点V到顶点W有一条路径，则说V和W是连通的连通图——图中任意两个顶点都是连通的连通分量——非连通图的每一个连通部分强连通图——有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图7.2图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示Aij={0(i,j)VR1(i,j)VR一、图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为ABCDEFA010010B100011C000101D001001E110000F011100有向图的邻接矩阵为非对称矩阵ABECDABCDEA01001B00100C00010D11000E001005735487214263816例1452375318642网络的邻接矩阵可定义为：，其它0E(G)v,v或)v,(v若,],[jijiijjiA∞typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点信息AdjMatrixarcs;//弧的信息intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph;typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_N][MAX_VERTEX_N];特点：•无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2•有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²•无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和或第i列元素之和•有向图中，–顶点Vi的出度是A中第i行元素之和–顶点Vi的入度是A中第i列元素之和二、图的邻接表存储表示邻接表(AdjacencyList)是一种链式存储结构。对于图G中的每个顶点vi建立一个单链表，存储该顶点的所有邻接点及其关系信息。每个单链表设一个头结点，称为顶点结点，单链表中的结点称为表结点，第i个结点表示该顶点的第i个邻接点。第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。二、图的邻接表存储表示每个表结点由三个域组成：adjvexnextarcinfo邻接点域(adjvex)：与顶点vi邻接的点在图中的位置；链域(nextarc)：指向依附于顶点vi的下一条边或弧的指针数据域(info)：边或弧相关信息的指针。datafirstarc顶点结点中有两个域：链域(firstarc)：指向链表中第一个结点，数据域(data)：存储顶点vi的名或其它有关信息的。typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;adjvexnextarcinfo表结点结构typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc顶点的结点结构typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//图的种类标志}ALGraph;图的结构定义0A141B0452C353D254E015F123BACDFE无向图的邻接表存储表示实质：将矩阵的每一行转化为一个链表，每个结点的度为其邻接表的长度特点：设无向图中顶点数位n，边数为e，则它的邻接表需要n个头结点和2e个表头结点142301201234ABCDE有向图的邻接表ABECF1.N个顶点，e条弧的有向图，需n个表头结点，e个表结点。2.第i条链表上的结点数，为Vi的出度。3.求顶点的出度易，求入度难。在第i条链表上的结点是以i为弧尾的各个弧头顶点ABECD有向图的逆邻接表ABCDE30342001234在第i条链表上的结点是以i为弧头的各个弧头顶点。1.N个顶点，e条弧的有向图，需n个表头结点，e个表结点。2.第i条链表上的结点数，为Vi的入度。3.求顶点的入度易，求出度难。三、有向图的十字链表存储表示弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧尾的结点指向下一个有相同弧头的结点typedefstructArcBox{//弧的结构表示inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;}VexNode;可看作是将有向图的邻接表和逆邻接表结合的一种链表顶点的结点结构顶点数据指向该顶点的第一条入弧指向该顶点的第一条出弧typedefstructVexNode{//顶点的结构表示VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;有向图的结构表示(十字链表)例bdacabcd123413123431434241^^^^^^^^四、无向图的邻接多重表存储表示typedefstructEbox{VisitIfmark;//访问标记intivex,jvex;//该边依附的两个顶点的位置structEBox*ilink,*jlink;InfoType*info;//该边信息指针}EBox;边的结构表示typedefstruct{//邻接多重表VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;}AMLGraph;顶点的结构表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;无向图的结构表示例aecbd1234acdb5e121434323552^^^^^说明在图的存储结构中，只有图的邻接矩阵是唯一的，而图的邻接表、十字链表和邻接多重表可能有多种，它取决于插入结点的顺序及读入边的顺序。7.3图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索遍历应用举例算法步骤：(1)从图中某个顶点V0出发，访问此顶点;(2)依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图;(3)直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图连通图的深度优先搜索遍历Vw1SG1SG2SG3W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3w2从上页的图解可见:1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志visited[w]”。2.如何判别V的邻接点是否被访问？深度优先搜索过程搜索回溯ACDEGBFIH123458967深度优先遍历序列：ABEGCFDHIACDEGBFIH123456789深度优先生成树voidDFS(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//若用邻接矩阵存储图for(w=0;wG.vexnum;i++)if(G.arcs[v][w]!=0&&!visited[w])DFS(G,w);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}voidBFSTraverse(GraphG,Status(*Visit)(intv)){//对图进行广度优先遍历for(v=0;vG.vexnum;++v)visited[v]=FALSE;//初始化访问标志InitQueue(Q);//置空的辅助队列Qfor(v=0;vG.vexnum;++v)if(!visited[v]){//v尚未访问}}//BFSTraverse……visited[v]=TRUE;Visit(v);//访问vEnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;Visit(w);EnQueue(Q,w);//访问的顶点w入队列}//if}//while三、遍历应用举例1.求一条从顶点i到顶点s的简单路径2.求两个顶点之间的一条路径长度最短的路径1.求一条从顶点i到顶点s的简单路径abchdekfg求从顶点b到顶点k的一条简单路径。从顶点b出发进行深度优先搜索遍历。例如:假设找到的第一个邻接点是a，则得到的结点访问序列为:badhcekfg。假设找到的第一个邻接点是c，则得到的结点访问序列为:bchdaekfg，1.从顶点i到顶点