数据结构(C描述)电子教案第7章.ppt
《数据结构(C描述)电子教案第7章.ppt》由会员分享,可在线阅读,更多相关《数据结构(C描述)电子教案第7章.ppt(77页珍藏版)》请在三一文库上搜索。
1、第7章 图,数据结构(C+描述),目录,7.6拓扑排序,7.1 图的基本概念,7.2 图的存贮结构,7.3 图的遍历,7.4 生成树和最小生成树,7.5最短路径,退出,7.1 图的基本概念,7.1.1 图的定义,图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:G=(V,E)。,例如,对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:G1=(V1,E1), 其中 V1=a,b,c,d,E1=(a,b),(a,c),(a,d),(b,d),(c,d),而G2=(V2,E2),其中V2=1,2,3, E2=,。,7.1.2 图的基本术语,1.
2、有向图和无向图,在图中,若用箭头标明了边是有方向性的,则称这样的图为有向图,否则称为无向图。如图7-1中,G1为无向图,G2为有向图。 在无向图中,一条边(x,y)与(y,x)表示的结果相同,用圆括号表示,在有向图中,一条边与表示的结果不相同,故用尖括号表示。x,y表示从顶点x发向顶点y的边,x为始点,y为终点。有向边也称为弧,x为弧尾,y为弧头,则x,y表示为一条弧,而y,x表示y为弧尾,x为弧头的另一条弧 。,2. 完全图、稠密图、稀疏图,具有n个顶点,n(n-1)/2条边的图,称为完全无向图,具有n个顶点,n(n-1) 条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。,
3、对于一般无向图,顶点数为n,边数为e,则 0e n(n-1)/2。 对于一般有向图,顶点数为n,弧数为e, 则 0en(n-1) 。 当一个图接近完全图时,则称它为稠密图,相反地,当一个图中含有较少的边或弧时,则称它为稀疏图。,3. 度、入度、出度,在图中,一个顶点依附的边或弧的数目,称为该顶点的度。在有向图中,一个顶点依附的弧头数目,称为该顶点的入度。一个顶点依附的弧尾数目,称为该顶点的出度,某个顶点的入度和出度之和称为该顶点的度。,另外,若图中有n个顶点,e条边或弧,第i个顶点的度为di,则有e=,4. 子图,若有两个图G1和G2, G1=(V1,E1), G2=(V2,E2), 满足如下
4、条件: V2V1 ,E2 E1,即V2为V1的子集,E2为E1的子集,称图G2为图G1的子图。,图和子图的示例具体见图7-2。,5 权,在图的边或弧中给出相关的数,称为权。 权可以代表一个顶点到另一个顶点的距离,耗费等,带权图一般称为网。,带权图的示例具体见图7-3。,6 连通图和强连通图,在无向图中,若从顶点i到顶点j有路径,则称顶点i和顶点j是连通的。若任意两个顶点都是连通的,则称此无向图为连通图,否则称为非连通图。,连通图和非连通图示例见图7-4。,在有向图中,若从顶点i到顶点j有路径,则称从顶点i和顶点j是连通的,若图中任意两个顶点都是连通的,则称此有向图为强连通图,否则称为非强连通图
5、。,强连通图和非强连通图示例见图7-5。,7 连通分量和强连通分量,无向图中,极大的连通子图为该图的连通分量。显然,任何连通图的连通分量只有一个,即它本身,而非连通图有多个连通分量。,对于图7-4 中的非连通图,它的连通分量见图7-6。,有向图中,极大的强连通子图为该 图的强连通分量。显然,任何强连通图的强连通分量只有一个,即它本身,而非强连通图有多个强连通分量。,对于图7-5 中的非强连通图,它的强连通分量见图7-7。,8路径、回路,在无向图G中,若存在一个顶点序列Vp ,Vi1,Vi2,Vin,Vq, 使得(Vp,Vi1),(Vi1,Vi2),,(Vin,Vq)均属于E(G),则称顶点Vp
6、到Vq存在一条路径。若一条路径上除起点和终点可以相同外,其余顶点均不相同,则称此路径为简单路径。起点和终点相同的路径称为回路,简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。,9 有根图,在一个有向图中,若从顶点V有路径可以到达图中的其它所有顶点,则称此有向图为有根图,顶点V称作图的根。,10 生成树、生成森林,连通图的生成树是一个极小连通子图,它包含图中全部n个顶点和n-1条不构成回路的边。非边通图的生成树则组成一个生成森林。若图中有n个顶点,m个连通分量,则生成森林中有n-m条边。,7.2 图的存贮结构,7.2.1 邻接矩阵,1 图的邻接矩阵表示,在邻接矩阵表示中
7、,除了存放顶点本身信息外,还用一个矩阵表示各个顶点之间的关系。若(i,j)E(G)或i,jE(G),则矩阵中第i行 第j列元素值为1,否则为0 。,图的邻接矩阵定义为: 1 若(i,j)E(G)或i,jE(G) Aij= 0 其它情形,例如, 对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。,2 从无向图的邻接矩阵可以得出如下结论,(1)矩阵是对称的; (2)第i行或第i 列1的个数为顶点i 的度; (3)矩阵中1的个数的一半为图中边的数目; (4)很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。,3 从有向图的邻接矩阵可以得出如下结论,(1) 矩阵不一定是
8、对称的; (2) 第i 行中1的个数为顶点i 的出度; (3) 第i列中1的个数为顶点 i的入度; (4) 矩阵中1的个数为图中弧的数目; (5) 很容易判断顶点i 和顶点j 是否有弧相连.,4 网的邻接矩阵表示,类似地可以定义网的邻接矩阵为: wij 若(i,j)E(G)或i,jE(G) Aij= 0 若i=j 其它情形 网及网的邻接矩阵见图7-10。,5 图的邻接矩阵数据类型描述,图的邻接矩阵数据类型描述如下: const int n= maxn; / 图中顶点数 const int e=maxe ; / 图中边数 struct graph elemtype Vn+1; / 存放顶点信息v
9、1,v2,.vn,不使用v0存储空间 int arcsn+1n+1 / 邻接矩阵 ;,6 建立无向图的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O(n2)。,7.建立有向图的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O(n2)。,8.建立无向网的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O(n2)。,9.建立有向网的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O(n2)。,7.2.2 邻接表,1 图的邻接表表示,将每个结点的边用一个单链表链接起来,若干个结点可以得到若干个单链表,每个单
10、链表都有一个头结点,所有头结点组成一个一维数组,称这样的链表为邻接表。 例如,图7-8所示的无向图G3和有向图G4的邻接表见图7-11所示,2 从无向图的邻接表可以得到如下结论,(1)第i 个链表中结点数目为顶点i的度; (2)所有链表中结点数目的一半为图中边数; (3)占用的存储单元数目为n+2e 。,3 从有向图的邻接表可以得到如下结论,(1)第i 个链表中结点数目为顶点i的出度; (2)所有链表中结点数目为图中弧数; (3)占用的存储单元数目为n+e 。,从有向图的邻接表可知,不能求出顶点的入度。为此,我们必须另外建立有向图的逆邻接表,以便求出每一个顶点的入度。逆邻接表在图7-11(c)
11、中已经给出,从该图中可知。有向图的逆邻接表与邻接表类似,只是它是从入度考虑结点,而不是从出度考虑结点。,4 图的邻接表数据类型描述,图的邻接表数据类型描述如下: const int n =maxn; / maxn表示图中最大顶点数 const int e= maxe ; / maxe图中最大边数 struct link /定义链表类型 elemtype data ; link *next ; struct node /定义邻接表的表头类型 elemtype v; /顶点信息 link *next; an+1;,5.无向图的邻接表建立,void creatlink( ) int i,j,k ;
12、link *s ; for(i=1; iij ; /输入一条边 (i,j) s=new link; /申请一个动态存储单元 sdata=j ; s-next=ai.next ;ai.next=s ; s=new link; s-data=i ; s-next=aj.next ;aj.next=s ;,该算法的时间复杂度为O(n+e)。,6.有向图的邻接表建立,void creatlink( ) int i,j,k ; link *s ; for(i=1; iij ; /输入一条边 s=new link; /申请一个动态存储单元 sdata=j ;s-next=ai.next ; ai.next
13、=s ; 该算法的时间复杂度为O(n+e)。,7.网的邻接表的数据类型描述,网的邻接表的数据类型可描述如下: const int n =maxn; / maxn表示网中最大顶点数 const int e= maxe ; / maxe网中最大边数 struct link /定义链表类型 elemtype data ; float w; /定义网上的权值类型为浮点型 link *next ; struct node /定义邻接表的表头类型 elemtype v; /顶点信息 link *next; an+1;,8 无向网的邻接表建立,void creatlink( ) float w; int i
14、,j,k ; link *s ; for(i=1; iijw ; /输入一条边 (i,j)及该边上的权值 s=new link; /申请一个动态存储单元 sdata=j ;s-w=w; s-next=ai.next ;ai.next=s ;s=new link; s-data=i ;s-w=w;s-next=aj.next ; aj.next=s ; 该算法的时间复杂度为O(n+e)。,9 有向网的邻接表建立,void creatlink( ) float w;int i,j,k ; link *s ; for(i=1; iijw ; /输入一条弧 及该弧上的权值 s=new link; /申
15、请一个动态存储单元 sdata=j ;s-w=w; s-next=ai.next ; ai.next=s ; 该算法的时间复杂度为O(n+e)。,另外,请注意上面的算法中,建立的邻接表不是唯一的,与你从键盘输入边的顺序有关,输入的边的顺序不同,则得到的链表也不同。,7.2.3 邻接多重表,在无向图的邻接表中,每条边(Vi,Vj)由两个结点表示,一个结点在第i个链表中,另一个结点在第j个链表中,当需要对边进行操作时,就需要找到表示同一条边的两个结点,这给操作带来不便,在这种情况下采用邻接多重表较方便。 在邻接多重表中,每条边用一个结点表示,每个结点由五个域组成,其结点结构为 :,其中mark为标
16、志域,用来标记这条边是否被访问过,i和j域为一条边的两个顶点,next1 和next2为两个指针域,分别指向依附于i顶点的下一条边和j顶点的下一条边。而表头与邻接表的表头类似。 邻接多重表的形式见图7-12。,7.3 图的遍历,和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图,则从图中任一顶点出发顺着边可以访问到该图中所有的顶点,但是,在图中有回路,从图中某一顶点出发访问图中其它顶点时,可能又会回到出发点,而图中可能还剩余有顶点没有访问到,因此,图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组visited来标志某个顶点是否被访
17、过,未访问的值为0,访问过的值为1。根据搜索路径的方向不同,图的遍历有两种方法:深度优先搜索遍历和广度优先搜索遍历。,7.3.1深度优先搜索遍历 1 深度优先搜索思想,深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过,在G中任选一个顶点i作为遍历的初始点,则深度优先搜索遍历可定义如下: (1) 首先访问顶点i,并将其访问标记置为访问过,即visitedi=1; (2) 然后搜索与顶点i有边相连的下一个顶点j,若j未被访问过,则访问它,并将j的访问标记置为访问过,visitedj=1,然后从j开始重复此过程,若j已访问,再看与i有边相连的其它顶点; (3) 若与i有边
18、相连的顶点都被访问过,则退回到前一个访问顶点并重复刚才过程,直到图中所有顶点都被访问完止。,例如,对图7-13所示无向图G7,从顶点1出发的深度优先搜索遍历序列可有多种,下面仅给出三种,其它可作类似分析。 在无向图G7中,从顶点1出发的深度优先搜索遍历序列举三种为:,1, 2, 4, 8, 5, 6, 3, 7 1, 2, 5, 8, 4, 7, 3, 6 1, 3, 6, 8, 7, 4, 2, 5,2 连通图的深度优先搜索,若图是连通的或强连通的,则从图中某一个顶点出发可以访问到图中所有顶点,否则只能访问到一部分顶点。 另外,从刚才写出的遍历结果可以看出,从某一个顶点出发的遍历结果是不唯一
19、的。但是,若我们给定图的存贮结构,则从某一顶点出发的遍历结果应是唯一的。,(1) 用邻接矩阵实现图的深度优先搜索 以图7-13中无向图G7 为例,来说明算法的实现,G7的邻接矩阵见图7-14。,算法描述为下面形式:,void dfs (int i) / 从顶点i 出发遍历 int j; coutg.vi; /输出访问顶点 visitedi=1; /全局数组访问标记置1表示已经访问 for(j=1; j=n; j+) if (g.arcsi j= =1) ,用上述算法和无向图G7,可以描述从顶点1出发的深度优先搜索遍历过程,示意图见图7-15,其中实线表示下一层递归调用,虚线表示递归调用的返回。
20、 从图7-15中,可以得到从顶点1的遍历结果为 1, 2, 4, 8, 5, 6, 3, 7。同样可以分析出从其它顶点出发的遍历结果。,(2)用邻接表实现图的深度优先搜索 仍以图7-13中无向图G7 为例,来说明算法的实现,G7的邻接表见图7-16,,算法描述为下面形式: void dfs1(int i) link *p; coutdata) dfs1(p-data);p=p-next; ,用刚才算法及图7-16,可以描述从顶点7出发的深度优先搜索遍历示意图,见图7-17,其中实线表示下一层递归,虚线表示递归返回,箭头旁边数字表示调用的步骤。 于是,从顶点7出发的深度优先搜索遍历序列,从图7-
21、17中可得出为 7, 3, 1, 2, 4, 8, 5, 6。从其它顶点出发的深度优先搜索序列,请读者自已写出。,3非连通图的深度优先搜索,若图是非连通的或非强连通图,则从图中某一个顶点出发。不能用深度优先搜索访问到图中所有顶点,而只能访问到一个连通子图(既连通分量)或只能访问到一个强连通子图(既强连通分量)。这时,可以在每个连通分量或每个强连通分量中都选一个顶点,进行深度优先搜索遍历,最后将每个连通分量或每个强连通分量的遍历结果合起来,则得到整个非连通图的遍历结果。 遍历算法实现与连通图的只有一点不同,即对所有顶点进行循环,反复调用连通图的深度优先搜索遍历算法即可。具体实现如下:,for(i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 描述 电子 教案
链接地址:https://www.31doc.com/p-2157054.html