《数据结构(C语言版)》 第08章_图.ppt
《《数据结构(C语言版)》 第08章_图.ppt》由会员分享,可在线阅读,更多相关《《数据结构(C语言版)》 第08章_图.ppt(135页珍藏版)》请在三一文库上搜索。
1、第章 图,图的基本概念,图的基本运算,生成树与最小生成树,拓扑排序,图的基本存储结构,最短路径,关键路径,图的遍历,8.1 图的基本概念,一、图的定义,图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边(或弧)集合组成的一种数据结构,它可以形式化地表示为: 图(V,E) 其中V=x|x某个数据对象集,它是顶点的有穷非空集合;E=(x,y)|x,yV或E=|x,yV且P(x,y),它是顶点之间关系的有穷集合,也叫做边集合,P(x,y)表示从x到y的一条单向通路。,图的应用举例 例1 交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示;,
2、例2 电路图 顶点:元件 边:连接元件之间的线路,例3 通讯线路图 顶点:地点 边:地点间的连线,例4 各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系,通常,也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集,若E(G)为空,则图G只有顶点而没有边。,若图G中的每条边都是有方向的,则称G为有向图。在有向图中,一条有向边是由两个顶点组成的有序对,有序对通常用尖括号表示。例如,有序对表示一条由vi到vj的有向边。有向边又称为弧,弧的始点称为弧尾,弧的终点称为弧头。若图G中的每条边都是没有方向的,则称G为无向图。无向图中的边均是顶点的无序对,无序对通常用圆括
3、号表示。,图8-1,图8.1(a)表示的是有向图G1,该图的顶点集和边集分别为: V(G1)=v1,v2,v3,v4 E(G1)=,,例,有序对 : 用以为vi起点、以vj为终点 的有向线段表示,称为有向 边或弧;,例:图8-1,图8.1(b)表示的是无向图G2,该图的顶点集和边集分别为: V(G2)=v1,v2,v3,v4,v5 E(G2)=(vl,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v5),(v4,v5),无序对(vi,vj): 用连接顶点vi、vj的线段 表示,称为无向边;,在以后的讨论中,我们约定: (1)一条边中涉及的两个顶点必须不相同,即:若(vi,vj
4、)或是E(G)中的一条边,则要求vivj; (2)一对顶点间不能有相同方向的两条有向边; (3)一对顶点间不能有两条无向边,即只讨论简单的图。,若用n表示图中顶点的数目,用e表示图中边的数目,按照上述规定,容易得到下述结论:对于一个具有n个顶点的无向图,其边数e小于等于n(n-1)/2,边数恰好等于n(n-1)/2的无向图称为无向完全图;对于一个具有n个顶点的有向图,其边数e小于等于n(n-1),边数恰好等于n(n-1)的有向图称为有向完全图。也就是说完全图具有最多的边数,任意一对顶点间均有边相连。,二、完全图,例:图8-2,图8.2所示的G3与G4分别是具有4个顶点的无向完全图和有向完全图。
5、图G3共有4个顶点6条边;图G4共有4个顶点12条边。,若(vi,vj)是一条无向边,则称顶点vi和vj互为邻接点 。,若是一条有向边,则称vi邻接到vj,vj邻接于vi,并称有向边关联于vi与vj,或称有向边与顶点vi和vj相关联。,三、度、入度、出度,在图中,一个顶点的度就是与该顶点相关联的边的数目,顶点v的度记为D(v)。例如在图8.2(a)所示的无向图G3中,各顶点的度均为3。 若G为有向图,则把以顶点v为终点的边的数目称为顶点v的入度,记为ID(v);把以顶点v为始点的边的数目称为v的出度,记为OD(v),有向图中顶点的度数等于顶点的入度与出度之和,即D(v)=ID(v)+OD(v)
6、。,无论有向图还是无向图,图中的每条边均关联于两个顶点,因此,顶点数n、边数e和度数之间有如下关系:,e=,.(式8-1),四、子图,给定两个图Gi和Gj,其中Gi=(Vi,Ei),Gj=(Vj,Ej),若满足ViVj,EiEj,则称Gi是Gj的子图。,v1,v1,子图示例,(a)无向图G3的部分子图,(b)有向图G4的部分子图,五、路径,无向图G中若存在着一个顶点序列v、v1、v2、vm、u,且(v,v1)、(v1,v2)、(vm,u)均属于E(G),则称该顶点序列为顶点v到顶点u的一条路径,相应地,顶点序列u、vm、vm-1、v1、v是顶点u到顶点v的一条路径。 如果G是有向图,路径也是有
7、向的,它由E(G)中的有向边、组成。路径长度是该路径上边或弧的数目。,如果一条路径上除了起点v和终点u相同外,其余顶点均不相同,则称此路径为一条简单路径。起点和终点相同(v=u)的简单路径称为简单回路或简单环。,六、连通图与强连通图,在无向图G中,若从顶点vi到顶点vj有路径,则称vi与vj是连通的。若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为连通图。例如,图8.1(b)所示的无向图G2、图8.2(a)所示的无向图G3是都是连通图。,无向图G的极大连通子图称为G的连通分量。根据连通分量的定义,可知任何连通图的连通分量是其自身,非连通的无向图有多个连通分量。,例:非连通图
8、及其连通分量示例,(a)非连通图G5 (b)G5的两个连通分量H1和H2,在有向图G中,若对于V(G)中任意两个不同的顶点vi和vj,都存在从vi到vj以及从vj到vi的路径,则称G是强连通图。,有向图的极大强连通子图称为G的强连通分量。根据强连通图的定义,可知强连通图的唯一强连通分量是其自身,而非强连通的有向图有多个强连分量。例如,图8.2(b)所示的有向图G4是一个具有4个顶点的强连通图,图8.5(a)所示的有向图G6不是强连通图(v2、v3、v4没有到达v1的路径),它的两个强连通分量H3与H4如图8.5(b)所示。,七、网络,有时在图的每条边上附上相关的数值,这种与图的边相关的数值叫权
9、。,权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权,则称这种带权图为网络。,作业:,8.1 对于无向图8.29,试给出 (1)图中每个顶点的度; (2)该图的邻接矩阵; (4)该图的连通分量。,v0,v3,v4,v2,v1,v5,v6,图8.29 无向图,8.2 给定有向图8.30,试给出 (1)顶点D的入度与出度; (2)该图的出边表与入边表; (3)该图的强连通分量。,A,B,C,D,E,图8.30 有向图,8.2 图的基本运算,图是一种复杂数据结构,由图的定义及图的一组基本操作构成了图的抽象数据类型。 ADT Graph 数据对象V:V是具有相同特性的数
10、据元素的集合,称为顶点集。 数据关系R: R=|v,wV且P(v,w),P(v,w)定义了边(或弧)(v,w)的信息,图的基本操作如下: (1)creatgraph(&g) 创建一个图的存储结构。 (2)insertvertex(&g,v) 在图g中增加一个顶点v。 (3)deletevertex(&g,v) 在图g中删除顶点v及所有和顶点v相关联的边或弧。 (4)insertedge(&g,v,u) 在图g中增加一条从顶点v到顶点u的边或弧。 (5)deleteedge(&g,v,u) 在图g中删除一条从顶点v到顶点u的边或弧。,(6)trave(g) 遍历图g。 (7)locatevert
11、ex(g,v) 求顶点v在图g中的位序。 (8)fiirstvertex(g,v) 求图g中顶点v的第一个邻接点。 (9)degree(g,v) 求图g中顶点v的度数。 (10)nextvertex(g,v,w) 求图g中与顶点v相邻接的顶点w的下一个邻接点。即求图g中顶点v的某个邻接点,它的存储顺序排在邻接点w的存储位置之后。 ADT Graph,8.3图的基本存储结构,图的存储结构至少要保存两类信息: 1)顶点的数据 2)顶点间的关系,约定: G=是图, V=v0,v1,v2, vn-1 ,设顶点的 角标为它的编号,8.3.1邻接矩阵及其实现,给定图G=(V,E),其中V(G)=v0,vi
12、,vn-1,G的邻接矩阵(Adacency Matrix)是具有如下性质的n阶方阵:,无向图的邻接矩阵是对称的,有向图的邻接矩阵可能是不对称的。,一、非网络的邻接矩阵,图的邻接矩阵示例,用邻接矩阵表示图,很容易判定任意两个顶点之间是否有边相连,并求得各个顶点的度数。对于无向图,顶点vi的度数是邻接矩阵中第i行或第i列值为1的元素个数,即:,D(vi)= = (8-2),对于有向图,邻接矩阵中第i行值为1的元素个数为顶点vi的出度,第i列值为1的元素的个数为顶点vi的入度,即:,OD(vi)= ; ID(vi) = (8-3),二、网络的邻接矩阵,当G=(V,E)是一个网络时,G的邻接矩阵是具有
13、如下性质的n阶方阵:,其中Wij表示边上的权值;表示一个计算机允许的、大于所有边上权值的数。,网络的邻接矩阵示例,邻接矩阵存储结构,#define FINITY 5000 /*此处用5000代表无穷大*/ #define m 20 /*最大顶点数*/ typedef char vertextype; /*顶点值类型*/ typedef int edgetype; /*权值类型*/ typedef struct vertextype vexsm; /*顶点信息域*/ edgetype edgesmm; /*邻接矩阵*/ int n,e; /*图中顶点总数与边数*/ mgraph; /*邻接矩阵表
14、示的图类型*/,文件名:mgraph.h,/*/ /* 图的邻接矩阵创建算法 */ /* 文件名:c_ljjz.c 函数名:creatmgraph1() */ /*/ #include #include “mgraph.h“ void creatmgraph1(mgraph *g) int i,j,k,w; /*建立有向网络的邻接矩阵存储结构*/ printf(“please input n and e:n“); scanf(“%d%d“,for(i=0;in;i+) /*输入图中的顶点值*/ g-vexsi=getchar(); for(i=0;in;i+) /*初始化邻接矩阵*/ for(
15、j=0;jn;j+) if (i=j) g-edgesij=0; else g-edgesij=FINITY; printf(“please input edges:n“); for (k=0;ke;k+) /*输入网络中的边*/ scanf(“%d%d%d“, 即可*/ ,说明: 当建立有向网时,边信息以三元组(i,j,w)的形式输入,i、j分别表示两顶点的序号,w表示边上的权。对于每一条输入的边信息(i,j,w),只需将g-edgesij赋值为w。 算法8.5中用到的creatmgraph2()是用于建立无向网络的函数,它与creatmgraph1()的区别在于对每一条输入的边信息(i,j
16、,w),需同时将g-edgesij 和g-edgesji赋值为w。 当建立非网络的存储结构时,所有的边信息只需按二元组(i,j)的形式输入。,8.3.2邻接表及其实现,用邻接矩阵表示法存储图,占用的存储单元个数只与图中顶点的个数有关,而与边的数目无关。一个含有n个顶点的图,如果其边数比n2少得多,那么它的邻接矩阵就会有很多空元素,浪费了存储空间。,无向图的邻接表 对于图G中的每个顶点vi,该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表,这个单链表就称为顶点vi的邻接表。单链表中的每个结点至少包含两个域,一个为邻接点域(adjvex),它指示与顶点vi邻接的顶点在图中的位序,另一个为链
17、域(next),它指示与顶点vi邻接的下一个结点。,为了便于随机访问任一顶点的邻接表,可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。,表头结点结构,边结点结构,对于无向图,vi的邻接表中每个表结点都对应于与vi相关联的一条边;对于有向图来说,如果每一顶点vi的邻接表中每个表结点都存储以vi的为始点射出的一条边,则称这种表为有向图的出边表(有向图的邻接表),反之,若每一顶点vi的邻接表中每个表结点都对应于以vi为终点的边(即射入vi的边),则称这种表为有向图的入边表(又称逆邻接表)。,在无向图的邻接表中,顶点vi的度为第
18、i个链表中结点的个数;而在有向图的出边表中,第i个链表中的结点个数是顶点vi的出度;为了求入度,必须对整个邻接表扫描一遍,所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。,V0的度为3,V0的出度为1,入度为2,邻接表的存储结构,/*/ /* 邻接表存储结构 文件名:adjgraph.h */ /*/ #define m 20 /*预定义图的最大顶点数*/ typedef char datatype; /*顶点信息数据类型*/ typedef struct node /*边表结点*/ int adjvex; /*邻接点*/ struct node *next; edgenode;,边
19、结点结构,typedef struct vnode /*头结点类型*/ datatype vertex; /*顶点信息*/ edgenode *firstedge; /*邻接链表头指针*/ vertexnode; typedef struct /*邻接表类型*/ vertexnode adjlist m; /*存放头结点的顺序表*/ int n,e; /*图的顶点数与边数*/ adjgraph;,头结点结构,/*/ /* 无向图的邻接表创建算法 */ /* 文件名c_ljb.c 函数名:createadjgraph() */ /*/ void createadjgraph(adjgraph *
20、g) int i,j,k; edgenode *s; printf(“Please input n and e:n“); scanf(“%d%d“,for(i=0;in;i+) scanf(“%c”, /*将新结点*s插入顶点vi的边表头部*/,s=(edgenode *)malloc(sizeof(edgenode); s-adjvex=i; /*邻接点序号为i*/ s-next=g-adjlistj.firstedge; g-adjlistj.firstedge=s; /*将新结点*s插入顶点vj的边表头部*/ 算法8.2 建立无向图的邻接表算法,说明:一个图的邻接矩阵表示是唯一的,但其邻
21、接表表示不唯一,这是因为在邻接表结构中,各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。,4 5 ABCD 0 1 0 2 0 3 1 2 2 3,例:若需建立下图所示的无向图邻接表存储结构,则在执行程序c_ljb.c时如果输入的信息为:,则将建立如下的邻接表存储结构。 A 321 B 20 C 310 D 20,8.3.3邻接多重表,在邻接多重表中,每一条边只有一个边结点。为有关边的处理提供了方便。 边结点的结构,其中,mark 是记录是否处理过的标记;vexi和vexj是依附于该边的两顶点位置。lniki域是链接指针,指向下一条依附于顶点vexi的边;linkj也是链接指针,指
22、向下一条依附于顶点vexj的边。需要时还可设置一个存放与该边相关的权值的域 cost。,顶点结点的结构 存储顶点信息的结点表以顺序表方式组织,每一个顶点结点有两个数据成员:其中,vertex 存放与该顶点相关的信息,firstedge 是指示第一条依附于该顶点的边的指针。 在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。 从顶点 i 出发, 可以循链找到所有依附于该顶点的边,也可以找到它的所有邻接顶点。,无向网络的邻接多重表示例,其中边表结点增加了一个存储权值的数据域 。,8.4 图的遍历,图的遍历:从图的某顶点出发,访问图中所有顶点,并且每个顶点仅访问一次。在图中,访问部分
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构C语言版 数据结构C语言版 第08章_图 数据结构 语言版 08
链接地址:https://www.31doc.com/p-3101920.html