第7章数据结构中的图.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,数据结构与应用,马石安 魏文平 编著,1,内容简介,本教材采用,面向对象,的观点讨论数据结构技术，并以,C+,类模板,作为算法描述工具。,教材在简要回顾,C+,程序设计概念的基础上，全面系统地介绍了,线性表、栈和队列、串、数组和广义表、树和二叉树及图,等数据结构，讨论了常用的,查找和排序,技术，对每一种数据结构，除了详细阐述其逻辑结构、存储结构和相关算法外，还对所有算法进行了,C+,语言实现和评价，并给出了应用实例。,教材附录给出了上机实验内容。,2,教材目录,第,0,章,C+,程序设计语言预备知识,0.1,一个简单,C+,语言程序,0.2,指针与引用,0.3,动态存贮分配,0.4,函数,0.5,类与对象,0.6,运算符重载,0.7,模板,3,第,1,章 绪论,1.1,数据结构的产生和发展,1.2,数据结构研究的内容,1.3,基本概念和术语,1.4,算法,第,2,章线性表,2.1,线性表的逻辑结构,2.2,线性表的顺序存储结构,2.3,线性表的链式存储结构,2.4,顺序表和链表的比较,2.5,线性表的应用,4,第章栈和队列,3.1,栈,3.2,队列,3.3,栈的应用,第,4,章 串,4.1,串的逻辑结构,4.2,串的顺序存储结构,4.3,串的链式存储结构,4.4,串的应用,5,第,5,章 数组和广义表,5.1,数组,5.2,矩阵的压缩存储,5.3,广义表,5.4,多维数组的应用,6,第,6,章 树和二叉树,6.1,树的逻辑结构,6.2,树的顺序存储结构,6.3,二叉树的逻辑结构,6.4,二叉树的存储结构,6.5,线索二叉树,6.6,树、森林与二叉树的转换,6.7,树的应用,7,第,7,章 图,7.1,图的逻辑结构,7.2,图的存储结构,7.3,图的遍历,7.4,生成树和最小生成树,7.5,最短路径,7.6 DAG,图及其应用,8,第,8,章 排序,8.1,概述,8.2,插入排序,8.3,交换排序,8.4,选择排序,8.5,归并排序,8.6,基数排序,8.7,各种内排序方法的比较和选择,9,第,9,章 查找,9.1,概述,9.2,线性表的查找,9.3,树表的查找,9.4,散列表的查找,附录 实验内容,10,第,7,章 图,11,7,.1,图的逻辑结构,7,.2,图的存储结构,7,.3,图的遍历,本章主要内容,7,.4,生成树和最小生成树,7,.5,最短路径,7,.6,DAG,图及其应用,12,7.1.1图的定义,7.1,图的逻辑结构,图,G,由结点的有穷非空集合,V,和边的有穷集合,E,组成，记为,G=(V,，,E),。在图结构中，将结点称为顶点，以便与树形结构加以区别，边则是顶点的偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。通常，也将图,G,的顶点集和边集分别记为,V(G),和,E(G),。,E(G),可以是空集，若,E(G),为空，则图,G,只有顶点而没有边。,13,7.1.2,图的基本术语,1.,有向图和无向图,如果,G,中的每条边都是有方向的，则称,G,为,有向图,。,在有向图中，一条有向边是由两个顶点组成的有序对，通常,用尖括号表示,。,例如，,表示一条有向边，,vi,是边的始点，,vj,是边的终点。,14,若图,G,中的每条边都是没有方向的，则称,G,为无向图。,无向图中的边均是顶点的无序对，通常用圆括号表示。无序对,(,vi,vj,),和,(,vj,vi,),表示同一条边。,15,无向图,G1,，在该图中：,V(G1)=v1,，,v2,，,v3,，,v4,，,v5,E(G1)=(v1,v2),，,(v1,v4),，,(v2,v3),，,(v2,v5),，,(v3,v4),，,(v3,v5),16,有向图,G2,，该图的顶点集和边集分别为：,V(G2)=v1,，,v2,，,v3,，,v4,，,v5,E(G2),，,，,，,17,2.,稠密图和稀疏图,3.,边和顶点的关系,若,(,v,i,v,j,),是一条无向边，则称顶点,v,i,和,v,j,互为邻接点,(adjacent),，或称,v,i,和,v,j,相邻接，并称,(,v,i,v,j,),依附或关联,(incident),于顶点,v,i,和,v,j,或称,(,v,i,v,j,),与顶点,v,i,和,v,j,相关联。,若,是一条有向边，则称此边是顶点,v,i,的一条出边，同时也是顶点,v,j,的一条入边；称顶点,v,i,邻接到,(,或邻接于,),顶点,v,j,，并称边,关联于,v,i,和,v,j,，或称,与顶点,v,i,和,v,j,相关联。,18,4.,顶点的度,无向图中顶点,v,的,度,是关联于该顶点的边的数目，记为,D(v,),。,在有向图中，以顶点,v,为终点的边的数目称为,v,的,入度,，记为,ID(v,),；以顶点,v,为始点的边的数目称为,v,的,出度,，记为,OD(v,),。顶点,v,的度定义为该顶点的入度和出度之和，即,D(v,)=,ID(v)+OD(v,),。,19,5.,子图,设,G=(V,，,E),是一个图，若,V,是,V,的子集，,E,是,E,的子集，且,E,的边所关联的顶点均在,V,中，则,G,=(V,，,E,),也是一个图，并称其为,G,的子图。,20,6.,路径,设,G,是图，若存在一个顶点序列,v,p,，,v,1,，,v,2,，,，,v,q-1,，,v,q,使得,(v,p,v,1,),，,(v,1,v,2,),，,，,(v,q-1,v,q,),属于,E,，则称,v,p,到,v,q,存在一条路径,(path),，其中,v,p,为起点，,v,q,为终点。,路径的长度是该路径上边的数目。,21,7.,有根图和图的根,8.,无向图的连通图和连通分量,9.,有向图的强连通图和强连通分量,10.,网络,22,7.1.3,图的基本操作,图的基本操作,:,图的初始化：,Create(),销毁图：,Destory,(),删除图中所有元素，回收图所占空间。,取顶点：,GetVex(i,),取图中的第,i,个顶点的数据信息。,23,插入顶点：,InsertVex(v,),在图中插入顶点,v,。,删除顶点：,DeleteVex(v,),删除图中顶点,v,。,插入边或弧：,Insert(v,w,),在图中插入一条边,(,v,w,),或弧,，如是无向图，还应增加对称边,(w,v),。,删除边或弧：,Delete(v,w,),24,7.2,图的存储结构,图的存储表示方法很多，,邻接矩阵表示法和邻接表表示法,是两种最常用的方法。,7.2.1,邻接矩阵,邻接矩阵是一种表示顶点之间相邻关系的矩阵。设,G=(V,，,E),是具有,n,个顶点的图，则,G,的邻接矩阵,A,是具有如下性质的,n,阶方阵：,25,对于无向图，若从顶点,vi,到,vj,有一条无向边,(,vi,vj,),，则,aij,=1,，,aji,=1;,否则,aij,=0,，,aji,=0,，故无向图的邻接矩阵是一个对称矩阵。对于有向图，若从顶点,vi,到,vj,有一条有向边,，则,aij,=1,；否则,aij,=0,。,26,27,28,基于邻接矩阵存储结构的图的类模板定义,cx7_1.h,29,邻接矩阵的基本操作及其实现,:,1,求顶点在图中的位置,2,创建图,3,顶点的增删,4,弧的增删,5,输出邻接矩阵,6,销毁有向图,30,7.2.2,邻接表,邻接表表示法是图的一种链接存储结构，类似于树的孩子链表表示法。,对于图,G,中的每个顶点,vi,，该方法把所有邻接于,vi,的顶点链成一个单链表，这个单链表就称为顶点,vi,的邻接表，邻接表中每个结点有两个域：其一是邻接点域,(,adjvex,),，用以存放与,vi,相邻接的顶点,vj,的序号,j,；其二是链域,(next),，用来指示与,vi,相邻接的下一顶点，从而将邻接表的所有表结点链在一起。,31,为每个顶点,vi,的邻接表设置一个头结点，头结点中包含两个域，其中一个是顶点域,vertex,，用来存放顶点,vi,的数据信息；另一个是指针域,firstedge,，它指向,vi,的邻接表的开始结点，相当于,vi,的邻接表的头指针。为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个一维数组中，称为顶点表，将其中的头结点称为顶点表结点。这样就构成了图的邻接表表示。,32,33,34,邻接表的基本操作及其实现,:,求顶点在图中的位置,创建有向图,顶点的增删,弧的增删,输出邻接表,销毁有向图,35,7.2.3,邻接矩阵和邻接表的比较,36,7.3,图的遍历,图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次的操作。,37,7.3.1,深度优先搜索遍历,深度优先搜索,(DFS),遍历类似于树的先序遍历。假定给定图,G,的初态是所有顶点均未曾访问过。则从图中某顶点,v,出发进行深度优先搜索遍历的基本思想是：,(1),访问顶点,v,；,(2),从,v,的未被访问的邻接点中选取一个顶点,w,，从,w,出发进行深度优先搜索遍历；,(3),重复上述两步，直至图中所有和,v,有路径相通的顶点都被访问到。,38,从图中某顶点,v,出发，,基于邻接矩阵表示,的深度优先搜索的递归过程如程序,sf7_13.cpp,所示。,从图中某顶点,v,出发，,基于邻接表表示,的深度优先搜索的递归过程如程序,sf7_15.cpp,所示。,39,无向图,G12,和它的深度优先搜索遍历,:,得到的顶点访问序列为：,v0 v1 v2 v5 v4 v6 v3 v7,40,7.3.2,广度优先搜索遍历,广度优先搜索,(breadth first,serch,，,BFS),遍历类似于树的层序遍历。,从图中某顶点,v,出发进行广度优先遍历的基本思想是：,(1),访问顶点,v,；,(2),依次访问,v,的各个未被访问的邻接点,v1,，,v2,，,，,vk,；,(3),分别从,v1,，,v2,，,，,vk,出发依次访问它们未被访问的邻接点，并使,“,先被访问顶点的邻接点,”,先于,“,后被访问顶点的邻接点,”,被访问，直至图中所有与顶点,v,有路径相通的顶点都被访问到。,41,无向图,G12,的广度优先搜索遍历,:,v0 v1 v3 v4 v2 v6 v5 v7,42,7.4,生成树和最小生成树,在图论中，常常将一个无回路的连通图定义为,树,。没有确定谁是根的图称为,自由树,。,7.4.1,生成树与生成森林,如果连通图,G,的一个子图是一棵包含,G,中所有顶点的树，则该子图称为,G,的生成树。,43,由深度优先搜索得到的生成树称为,深度优先生成树,，简称为,DFS,生成树；,由广度优先搜索得到的生成树称为,广度优先生成树,，简称为,BFS,生成树。,44,45,图的生成树不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。,46,7.4.2,最小生成树,带权的连通图也称连通网，其生成树也是带权的，我们把生成树各边的权值总和称为该生成树的权。,图的生成树不唯一，从不同的顶点出发遍历带权的连通图，可以得到不同的带权生成树，其中权值最小的生成树称为最小生成树，简称为,MST,。,47,普里姆,(Prim),算法,和,克鲁斯卡尔,(,Kruskal,),算法,是两个利用,MST,性质构造最小生成树的算法。,1,普里姆算法,假设,G=(V,E),是连通网络，,TE,是,G,上最小生成树中边的集合。算法从,V,中任取一个顶点作为源点,(,假定为,v,0,),，此时,U=v,0,(v,0,V),，,TE,开始，重复执行下述操作：在所有,u,U,，,v,V,-U,的边,(u,，,v),E,中找一条代价最小的边,(u,，,v),并入集合,TE,，同时,u,并入,U,，直至,U,V,为止。此时,TE,中必有,n-1,条边，则,T,(V,，,TE),为,G,的最小生成树。,48,49,50,51,52,采用邻接矩阵存储的,Prim,算法,sf7_20.cpp,53,2,克鲁斯卡尔算法,假设连通网,G,(V,，,E),，则令最小生成树的初始状态为只有,n,个顶点而无边的非连通图,T=(V,，,),，图中每个顶点自成一个连通分量。在,E,中选择权值最小的边，若该边依附的顶点落在,T,中不同的连通分量上，则将此边加入到,T,中，否则舍去此边而选择下一条权值最小的边。依次类推，直至,T,中所有顶点都在同一连通分量上为止。,54,55,56,57,克鲁斯卡尔算法,sf7_21.cpp,58,7.5,最短路径,7.5.1,单源最短路径,所谓单源最短路径：是指对已知图,G=(V,，,E),，给定源顶点,v,，找出,v,到其余各顶点的最短路径。,59,1.,迪杰斯特拉,(,Djikstra,),算法基本思想,迪杰斯特拉提出了按路径长度递增的次序逐一产生最短路径的算法：,首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。,60,设集合,S,存放已经求得最短路径的终点，则,V-S,为尚未求得最短路径的终点。初始状态时，集合,S,中只有一个源点，设为顶点,v,0,。迪杰斯特拉算法的具体做法是：首先产生从点,v,0,到自身的路径，其长度为,0,，将,v,0,加入,S,；算法的每一步上，按照最短路径值的递增次序，产生下一条最短路径，并将该路径的终点,v,j,V,-S,加入,S,；直到,S=V,，算法结束。,61,2.,算法描述,62,3.,算法实现,教材,sf7_22.cpp,63,7.5.2,所有顶点对之间的最短路径,1.,弗洛伊德算法思想,求从顶点,v,i,到,v,j,的最短路径。设集合,S,的初始状态为空集合。然后，依此向集合,S,中加入顶点,v,0,，,v,1,，,v,2,v,n-1,，每次加入一个顶点。用二维数组,dist,保存各条最短路径的长度，其中，,distij,为从,i,到,j,的当前最短路径长度。随着,S,中的顶点的不断增加，,distij,的值不断修正，当,S=V,时，,distij,的值就是从,i,到,j,的最短路径。,64,2.,算法描述,图,7.24,用弗洛伊德算法求带权有向网所有顶点对的最短路径,65,3.,算法实现,教材,sf7_23.cpp,66,7.6 DAG,图及其应用,一个无环的有向图称作有向无环图，简称,DAG,图。,DAG,图是一类比有向树更一般的特殊有向图。,67,7.6.2 AOV,网与拓扑排序,1,AOV,网,以有向图中的顶点表示活动，弧表示活动之间的优先关系，这样的有向图称为顶点表示活动的网，简称,AOV,网。,68,2,拓扑排序,设,G=(V,E),是一个具有,n,个顶点的有向图，,V,中的顶点序列,v0,，,v1,，,，,vn-1,称为一个拓扑序列，当且仅当满足下列条件：若从,vi,到顶点,vj,有一条路径，则在顶点序列中顶点,vi,必在顶点,vj,之前。对一个有向图构造拓扑序列的过程称为拓扑排序。,69,3,拓扑排序的实现,教材,sf7_24.cpp,70,7.6.3 AOE,网与关键路径,1.AOE,网,与,AOV,网对应的是,AOE(Activity,On Edge),网，即边表示活动的网。在,AOV,网中，有向图的顶点表示一项任务，有向边表示任务之间的先后关系。在实际应用中，任务之间除了先后关系外，还有时间上的约束，用,AOE,网来表示这种约束关系。,71,2,关键路径,在,AOE,网中，因为有些活动可以同时进行，所以完成一个工程所需的最短时间是从一个始点到一个终点的最大路径长度。具有最大长度的路径被称为关键路径,(critical path),。,72,3,关键路径的确定,教材,sf7_25.cpp,73,74,本章结束,75,