数据结构第 7 章 图@南京工程学院通信工程学院

《数据结构第 7 章 图@南京工程学院通信工程学院》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1数据结构课程的内容多对多（m:n) 27.1抽象数据类型图的定义7.2图的存储表示7.3图的遍历7.4最小生成树7.5重（双）连通图和关节点7.6两点之间的最短路径问题7.7拓扑排序7.8关键路径第七章图 3一、图的定义和术语图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对。有向图——有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)7.1抽象数据类型图的定义(u,v)V=VertexE=Edge 4例245136G1有向图G1=（V，E）中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26无向图G2=（V，E）中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}图的示例 5有向完全图——有n(n-1)条弧的n个顶点的有向图无向完全图——有n(n-1)/2条边的n个顶点的无向图稀疏图--若边或弧的个数e，若G是无向的，则还增添对称弧(w,v)。DeleteArc(&G,v,w);//在G中删除弧，若G是无向的，则还删除对称弧(w,v)。 16遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。 177.2图的存储表示1、数组(邻接矩阵)存储表示2、邻接表存储表示3、有向图的十字链表存储表示4、无向图的邻接多重表存储表示 18用两个数组分别存储顶点信息和顶点之间的关系信息(邻接矩阵—表示顶点间相邻关系的矩阵)定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A（二维数组）是具有以下性质的n阶方阵：例G12413例15324G21、图的数组(邻接矩阵)存储表示 19邻接矩阵特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和(第i行非0元素1的个数)例G12413例15324G2 20例1452375318642网的邻接矩阵示意图网的邻接矩阵可定义为：∞反之容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵法优点：邻接矩阵法缺点： 21typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型,//对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];图的数组(邻接矩阵)存储表示实现#defineINFINITYINT_MAX//定义无穷大∞#defineMAX_VERTEX_NUM20//定义图的类型{有向图,有向网,无向图,无向网}typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点数组AdjMatrixarcs;//邻接矩阵，可设二维intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph; 22例G12413例15324G2图的数组(邻接矩阵)存储表示实例（构建算法见教材P162）G1.vexs={1，2，3，4}；G1.arcs=G1.vexnum=4；G1.arcnum=4；G1.kind=DG；G2.vexs={[1，2，3，4，5}；G2.arcs=G2.vexnum=5；G2.arcnum=6；G2.kind=UDG；MGraphG1; 23表头结点结构:数据域（data）用于存储顶点的名或其它有关信息；链域（firstarc）用于指向链表中第一个顶点（即与顶点vi邻接的第一个邻接点）边表结点结构：adjvex与顶点vi邻接的点在图中的位置info存储和边相关的信息(若无，则置空NULL)nextarc指向下一条边的结点的指针表头结点弧结点datafirstarcadjvexinfonextarc2、图的邻接表存储表示实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）；同时为每一个单链表附设一个表头结点，并将所有的表头结点顺序存储（数组），以便随机访问任一顶点的链表。 24例G1bdac例aecbdG21234acdbvexdatafirstarc3241^^^^adjvexnextarc1234acdbvexdatafirstarc4212^^^adjvexnextarc5e435^15323^提示：在无向图，每一个边结点在图的单链表中出现两次，故无向图中若有n个顶点和e条边，则需要存储空间为：n+2e图的邻接表存储实例 25typedefstructArcNode//弧结点{intadjvex;//邻接点域，存放与Vi邻接的点在表头数组中的位置structnode*nextarc;//链域，指示依附于vi的下一条边或弧的结点，//VRTypeweight;InfoType*info;//定义与弧相关的权值，无权则为0}ArcNode;//定义指向该弧相关信息的指针typedefstructVNode//表头结点{VertexTypevexdata;//存放顶点信息structArcNode*firstarc;//指示第一个邻接点}VNode，AdjList[MAX_VERTEX_NUM];vexdatafirstarc图的邻接表存储表示typedefstruct{//图的结构定义AdjListvertices;//顶点向量intvexnum,arcnum;GraphKindkind;//图的种类标志}ALGraph;adjvexnextarcWeightinfo 26邻接表特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数（以vi为弧头）。为此需遍历整个邻接表。一种解决的方法是逆邻接表法 27一种解决的方法是逆邻接表法，我们可以对每一顶点vi再建立一个逆邻接表，即对每个顶点vi建立一个所有以顶点vi为弧头的弧的表，如图所示。图G1的邻接表和逆邻接表表示法例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnextarc1234acdbvexdatafirstarc2341^^^^adjvexnextarc 28练习：求下图各顶点的出度、入度，图的邻接矩阵、邻接表和逆邻接表图G1cdabe 29讨论：邻接表与邻接矩阵有什么异同之处？联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于该行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。e随n的改变而变化--函数关系3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<");//输入各边并构造邻接表scanf("%d,%d",&i,&j);s=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j;s->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;}} 31举例：建立有（无）向图的邻接表图的邻接表是应用较多的一种存储结构。从邻接表的结构定义可见，建立邻接表的主要操作是在链表中插入一个结点，以下是输入无向图的顶点和边建立邻接表的算法步骤。BCAFED0A411B5402C533D524E105F320依次输入的数据为：1.顶点、边数：67UDG2.顶点：ABCDEF3.边：ABAEBEBFCDCFDF头插法vexdatafirstarcadjvexnextarc 32举例：建立有（无）向图的邻接表（续）建立邻接表的主要操作是在链表中插入一个结点，以下是输入有向图的顶点和弧建立邻接表的算法。依次输入的数据为：1.57DG2.ABCDE3.ABAEBCCDDADBECABECD142301201234ABCDE尾插法 333、有向图的十字链表存储表示有向图的邻接表和逆邻接表组合 ABCABC012∧02∧∧0121∧20∧∧有向图十字链表表示示意图有向图的十字链表 35typedefstructArcNode{inttailvex,headvex;//弧尾、弧头在表头数组中位置structArcNode*hlink；//指向弧头相同的下一条弧structArcNode*tlink;//指向弧尾相同的下一条弧InfoType*info;//定义弧的相关信息，如权值}ArcNode;typedefstructVexNode{intdata;//存与顶点有关信息ArcNode*firstin；//指向以该顶点为弧头的第一个弧结点ArcNode*firstout;//指向以该顶点为弧尾的第一个弧结点}VexNode;datafirstinfirstout有向图的十字链表存储表示tailvexheadvexhlinktlinkinfo弧结点：顶点结点：typedefstruct{//图的定义VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph; 36类似于有向图的十字链表，若将无向图中表示同一条边的两个结点合在一起，将得到无向图的另一种表示方法--邻接多重表。例如4、无向图的邻接多重表存储表示BCAFED 37无向图的邻接多重表存储表示在邻接多重表中，每一条边用一个结点表示，边结点结构如下：markivexilinkjvexjlinkinfoconstMAX_VERTEX_NUM=20;typedefemnu{unvisited,visited}VisitIf;typedefstructEdgeNode{//边结点结构定义VisitIfmark;//访问标记intivex,jvex;//该边依附的两个顶点（vi，vj）在图中的位置structEdgeNode*ilink,*jlink;//分别指向依附这两个顶点的下一条边VRTypeweight;//与弧相关的权值，无权则为0InfoType*info;//与该边相关信息的指针};datafirstedge顶点结点：typedefstruct{//顶点结点结构定义VertexTypedata;EdgeNode*firstedge;//指向第一条依附该顶点的边}VexNode;typedefstruct{//多重链表结构定义VexNodeadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;//无向图的当前顶点数和边数GraphKindkind;//图的种类标志}AMLGraph; 38各种存贮结构的适用类型数组(邻接矩阵)：有向图和无向图邻接表（逆邻接表）：有向图和无向图十字链表：有向图邻接多重表：无向图 397.3图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。图的遍历（TraversingGraph）:V1V2V4V5V3V7V6V8例提示：前面学习过树的遍历有递归遍历（前序、中序和后序）和非递归算法演示提问：树的遍历能否用于图的遍历？能或不能为什么？不能！因为图有回路，若用树的遍历算法可能导致无限循环。为防止循环，可设置已访问标志。然而，图中可能有孤立点，若不加修改地使用树的遍历，就可能会遗漏图中的一部分顶点。 40为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此我们为图设置一个访问标志数组visited［n］:vi未被访问:visited[i]值为falsevi被访问过：visited［i］为true根据搜索路径方向不同：深度优先搜索（纵向↓）广度优先搜索（横向→）遍历应用举例V1V2V4V5V3V7V6V8例 41深度优先搜索(Depth-FirstSearch—DFS)是指按照深度方向搜索,它类似于树的先根遍历,是树的先根遍历的推广。深度优先搜索连通子图的基本思想是：假设图G初态为所有顶点未被访问（visited[i]=false），从G中任选一顶点vi：⑴、从该顶点vi出发,首先访问vi,,置visited[vi]=true;⑵、然后依次搜索vi的每一个邻接点vj；⑶、若vj未被访问过，则以vj为新的初始出发点，重复⑴若vj已被访问过，则返回到vi另一个邻接点，重复⑶⑷、如果经过⑴、⑵、⑶后,图中仍有未被访问的顶点,再从中任选一顶点,重复⑴、⑵、⑶,直至所有顶点都被访问过,遍历结束。一、深度优先搜索遍历图V1V2V4V5V3V7V6V8例无向图深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8例有向图 42V1V2V4V5V3V7V6V8例深度遍历：V11234v1v3v4v2vexdatafirstarc2783^^^adjvexnext5v5641^51282^v6v7v8678736354^^^V3V7V6V2V5V8V4思考题：按图的存储结构如何遍历？邻接矩阵如何？思想同算法vi=v11.访问V1。2.求Vi的邻接点Vj。3.若vj未被访问过，则以vj为新的初始出发点，重复⑴若vj已被访问过，则返回到vi另一个邻接点，重复⑶ 43V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍历：V1V3V7V6V2V4V8V5 44从上页的遍历过程可见:1.深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点v设立一个“访问标志visited[v]”。2.如何判别V的邻接点是否被访问？3.如何求V的邻接点？解决的办法是：根据图的存储结构来确定。对于邻接表而言，通过顶点向量和对应的单链表查找邻接点。 45深度优先遍历算法-递归算法开始访问V0,置标志求V0邻接点有邻接点w？求下一邻接点w→V0W访问过？返回NYNYDFS开始标志数组初始化Vi=0Vi访问过DFSVi=Vi+1Viv2,V1->v3的路径长度为1；V1->v4,V1->v5,V1->v6,V1->v7的路径长度为2；V1->v8的路径长度为3。V1V2V4V5V3V7V6V8例例如：广度遍历序列：V1V2V3V4V5V6V7V8 54为避免重复访问,需要一个辅助数组visited[n]，给被访问过的顶点加标记。为了实现逐层（按顶点的路径长度递增）访问,算法中需使用了一个队列,以记忆正在访问的这一层和下一层的顶点,以便于向下一层访问。 5512341342vexdatafirstarc5543^^^adjvexnext551^51143^220123451fr遍历序列：10123454fr遍历序列：1401234543fr遍历序列：143先访问后入队1出队，依次得到其所有邻接点，输出并进队例14235 5612341342vexdatafirstarc5543^^^adjvexnext551^51143^22012345432fr遍历序列：1432012345325fr遍历序列：143251的邻接点入队完毕，4出队，依次得到其所有未被访问的邻接点，输出并进队例14235 5701234525fr遍历序列：143250123455fr遍历序列：14325012345fr遍历序列：14325例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^22 58广度优先搜索遍历图算法流程图开始访问V,置标志求U邻接点WW存在吗U下一邻接点WW访问过结束NYNY初始化队列V入队队列空吗队头出队U访问W,置标志W入队NaaYBFS开始标志数组初始化Vi=0Vi访问过？BFSVi=Vi+1Vi83032V2:813-------133032V1:13--------------13302220V3:13---------------------192220V4:19终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj--------------------------------2120V6:20516432085623013717329求最短路径示例2： 83i<=G.vexnum初始化过程;(i=1;)EndNYw，则对应元素为权值；否则为逐步试着在原直接路径中增加中间顶点（依次为v0,v1,…），若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束二、每一对顶点之间的最短路径 85例ACB264311041160230初始：路径：ABACBABCCA046602370加入B：路径：ABABCBABCCACAB0411602370加入A：路径：ABACBABCCACAB046502370加入C：路径：ABABCBCABCCACAB求每一对顶点之间的最短路径的示例： 86算法实现图用邻接矩阵存储length[][]存放最短路径长度path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号算法描述例132264311初始：041160230length=011202300path=加入V1：0411602370length=011202310path=加入V2：046602370length=012202310path=加入V3：046502370length=012302310path=算法分析：T(n)=O(n³) 1给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。作业2.假设图的顶点是A、B……请根据下面的邻接矩阵画出相应的无向图或有向图。 3.分别给出如图所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。4.应用prim算法求图所示带权连通图的最小生成树。 89图存储结构遍历邻接矩阵邻接表十字链表邻接多重表深度优先搜索DFS广度优先搜索DFS无向图的应用应用图的连通分量图的生成树最小生成树Prim算法Kruskal算法有向(无环)图的应用最短路径Dijkstra算法Floyd算法（利用DFS）本章小结-体系结构图(利用DFS和BFS)AOV网,AOE网拓扑排序关键路径 901.熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。3.应用图的遍历算法求解各种简单路径问题。4.理解教科书中讨论的各种图的算法。本章小结（续）