C语言数据结构第06讲图.ppt
《C语言数据结构第06讲图.ppt》由会员分享,可在线阅读,更多相关《C语言数据结构第06讲图.ppt(59页珍藏版)》请在三一文库上搜索。
1、实用数据结构基础,第7章 图,第7章 图,知 识 点 图的逻辑结构及基本术语 邻接矩阵和邻接表的存储结构和特点 深度优先搜索和广度优先搜索两种遍历算法 图的连通性和生成树的概念 最短路径的含义及求最短路径的算法,难 点 图的遍历 最小生成树 最短路径 要 求 熟练掌握以下内容: 图的存储结构 图的遍历算法 了解以下内容: 图的最小生成树和求最小生成树算法 带权有向图的最短路径问题,第7章 目录,7-1 图的定义和术语 7-2 图的存储表示 7-3 图的遍历 7-4 图的连通性 7-5 最短路径 小 结 实验7 图子系统 习题7,7-1 图的定义和术语,图(Graph)是一种比树形结构更复杂的非
2、线性结构。在图形结构中,每个结点都可以有多个直接前驱和多个直接后继。 7-1 图的定义和术语 7-1-1 图的定义 图(Graph)是由非空的顶点(Vertices)集合和一个描述顶点之间关系边(Edges)的有限集合组成的一种数据结构。可以用二元组定义为: G(V,E) 其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。,图7-1 无向图G1,图7-2 有向图G2,G1=(V,E) Vv1,v2,v3,v4,v5; E(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)。 (vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线,也称
3、为边。,G2=(V,E) V=v1,v2,v3,v4 E=, 表示顶点vi和顶点vj之间有一条有向直接连线,也称为弧。其中vi称为弧尾,vj称为弧头。,7-1-2 图的相关术语 (1)无向图(Undigraph) 在一个图中,如果每条边都没有方向(如图7-1),则称该图为无向图。 (2)有向图(Digraph) 在一个图中,如果每条边都有方向(如图7-2),则称该图为有向图。 (3)无向完全图 在一个无向图中,如果任意两顶点都有一条直接边相连接,则称该图为无向完全图。可以证明,在一个含有n个顶点的无向完全图中,有n (n-1)/2条边。,(4)有向完全图 在一个有向图中,如果任意两顶点之间都有
4、方向互为相反的两条弧相连接,则称该图为有向完全图。在一个含有n个顶点的有向完全图中,有n (n-1) 条弧。 (5)稠密图、稀疏图 我们称边数很多的图为稠密图;称边数很少的图为稀疏图。 (6)顶点的度 在无向图中:一个顶点拥有的边数,称为该顶点的度。记为TD (v)。,在有向图中: (a) 一个顶点拥有的弧头的数目,称为该顶点的入度, 记为ID (v); (b) 一个顶点拥有的弧尾的数目,称为该顶点的出度, 记为OD (v); (c) 一个顶点度等于顶点的入度+出度, 即:TD (v)=ID (v)OD (v)。 在图7-1的G1中有: TD(v1)=2 TD(v2)=3 TD(v3)=3 T
5、D(v4)=2 TD(v5)=2 在图7-2的G2中有: ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2,可以证明,对于具有n个顶点、e条边的图,顶点vi的度TD (vi)与顶点的个数以及边的数目满足关系: (7)权 图的边或弧有时具有与它有关的数据信息,这个数据信息就称为权(Weight)。,(8)网边(或弧)上带权的图称为网(Network)。 如图7-3所示,就是一个无向网。如果边是有方向的带权图,则就是一个有向网。,图7
6、-3 一个无向网示意,图7-3 一个无向网示意,(9)路径、路径长度 顶点vi到顶点vj之间的路径是指顶点序列vi,vi1,vi2, , vim,vj.。其中,(vi,vi1),(vi1,vi2),, (vim,.vj)分别为图中的边。路径上边的数目称为路径长度。 在图7-1的无向图G1中,v1v4v3v5与v1v2v5是从顶点v1 到顶点v5 的两条路径,路径长度分别为3和2。 (10)回路、简单路径、简单回路 在一条路径中,如果其起始点和终止点是同一顶点,则称其为回路或者环。如果一条路径上所有顶点除起始点和终止点外彼此都是不同的,则称该路径为简单路径。 在图7-1中,前面提到的v1到v5的
7、两条路径都为简单路径。除起始点和终止点外,其他顶点不重复出现的回路称为简单回路,或者简单环。如图7-2中的v1v3v4v1。,(11)子图 对于图G=(V,E),G=(V,E),若存在V是V的子集 ,E是E的子集 ,则称图G是G的一个子图。 图7-4示出了G1和G2的子图。,图7-4 图G1和G2的两个子图示意,(a) G1的子图 (b) G2的子图,图7-1 无向图G1,(12)连通图、连通分量 在无向图中,如果从一个顶点vi到另一个顶点vj(ij)有路径,则称顶点vi和vj是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。图7-5 (a)中有两个连通分量,如图7
8、-5 (b)所示。,(a) 无向图G3 (b) G3的两个连通分量 图7-5 无向图及连通分量示意,(13)强连通图、强连通分量 对于有向图来说,若图中任意一对顶点vi 和vj(ij)均有从一个顶点vi到另一个顶点vj有路径,也有从vj到vi的路径,则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。 图7-2中有两个强连通分量,分别是v1,v2,v3和v4,如图7-6所示。,(14)生成树 连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树(Spanning Tree)。在生成树中添加任意一条属于原图中的边必定会产生回路,因为新添加的边使其所依附的两个顶点之间
9、有了第二条路径。若生成树中减少任意一条边,则必然成为非连通的。n个顶点的生成树具有n-1条边。,V1,V3,V2,V4,图7-6 有向图G2的两个 强连通分量示意,7-1-3 图的基本操作 图的基本操作有: (1)CreatGraph(G)输入图G的顶点和边,建立图G的存储。 (2)DFSTraverse(G,v)在图G中,从顶点v出发深度优先遍历图G。 (3)BFSTtaverse(G,v)在图G中,从顶点v出发广度优先遍历图G。,图的存储结构比较多。对于图的存储结构的选择取决于具体的应用和需要进行的运算。 下面介绍几种常用的图的存储结构。,7-2 图的存储表示,邻接矩阵是表示顶点之间相邻关
10、系的矩阵。 假设图G(V,E)有n个顶点,即Vv0,v1,vn-1,则G的邻接矩阵是具有如下性质的n阶方阵: 1 若(vi,vj)或是E(G)中的边 Aij= 0 若(vi,vj)或不是E(G)中的边 若G是网,则邻接矩阵可定义为: wij 若(vi,vj)或是E(G)中的边 Aij= 0或 若(vi,vj)或不是E(G)中的边 其中,wij表示边(vi,vj)或上的权值(如图7-3);表示一个计算机允许的、大于所有边上权值的数。,用邻接矩阵表示法如图7-7所示;用邻接矩阵表示法如图7-8所示。,图的邻接矩阵具有以下性质: (1)无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时只
11、需存放上(或下)三角矩阵的元素即可。 (2)对于无向图,邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点的度TD(vi)。 (3)对于有向图,邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点的出度OD(vi)(或入度ID(vi))。 (4)用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连;但是,要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。,图的邻接矩阵存储的描述如下: #define MAXLEN 10 typedef struct char vexsMAXLEN; i
12、nt edgesMAXLENMAXLEN; int n,e; MGraph;,建立一个图的邻接矩阵存储的算法如下: void CreateMGraph(MGraph *G) int i,j,k; char ch1,ch2; printf(“请输入顶点数和边数(输入格式为:顶点数,边数):n“); scanf(“%d,%d“,printf (“请输入每条边对应的两个顶点的序号(输入格式为:i,j):n“); for(k=0;ke;k+) getchar(); printf (“请输入第%d条边的顶点序号:“,k+1); scanf (“%c,%c“, ,7-2-2 邻接表 邻接表(Adjacen
13、cy List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi,该方法将所有邻接于vi的顶点vj链成一个单链表,这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中,就构成了图的邻接表。 在邻接表表示中有两种结点结构,如图7-9所示。 顶点域 边表头指针 邻接点域 指针域 顶点表 边表 图7-9 邻接矩阵表示的结点结构,一种是顶点表的结点结构,它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成,另一种是边表结点,它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。对于网
14、的边表需再增设一个存储边上信息(如权值等)的域(info),网的边表结构如图7-10所示。 邻接点域 边上信息 指针域 图7-10 网的边表结构,图7-11给出无向图7-7对应的邻接表表示。,邻接表表示形式描述如下:,define MAXLEN 10 / 最大顶点数为10 typedef struct node / 边表结点 int adjvex; / 邻接点域 struct node * next; / 指向下一个邻接点的指针域 /若要表示边上信息,则应增加一个数据域info EdgeNode; typedef struct vnode / 顶点表结点 VertexType vertex;
15、/ 顶点域 EdgeNode * firstedge; / 边表头指针 VertexNode; typedef VertexNode AdjListMAXLEN; / AdjList是邻接表类型 typedef struct AdjList adjlist; / 接表 int n,e; / 顶点数和边数 ALGraph; / ALGraph是以邻接表方式存储的图类型,建立一个有向图的邻接表存储的算法如下: void CreateGraphAL (ALGraph *G) int i,j,k; EdgeNode * s; printf(“请输入顶点数和边数(输入格式为:顶点数,边数) :n“);
16、scanf(“%d,%d“, ,若无向图中有n 个顶点、e条边,则它的邻接表需n个头结点和2e个表结点。显然,在边稀疏(en(n-1)/2)的情况下,用邻接表表示图比邻接矩阵节省存储空间,当和边相关的信息较多时更是如此。 在无向图的邻接表中,顶点vi的度恰为第i个链表中的结点数;但在有向图中,第i个链表中的结点个数只是顶点vi的出度。如果要求入度,则必须遍历整个邻接表才能得到结果。有时,为了便于确定顶点的入度或以顶点vi为头的弧,可以建立一个有向图的逆邻接表,即对每个顶点vi 建立一个链接,以vi为弧头的弧的链表。例如图7-12所示为有向图G2(图7-2)的邻接表和逆邻接表。,在建立邻接表或逆
17、邻接表时,若输入的顶点信息即为顶点的编号,则建立邻接表的复杂度为O(n+e),否则,需要通过查找才能得到顶点在图中位置,则时间复杂度为O(n*e)。,7-3 图的遍历,图的遍历(traversing graph)是指从图中的某一顶点出发,对图中的所有顶点访问一次,而且仅访问一次。图的遍历是图的一种基本操作。由于图结构本身的复杂性,所以图的遍历操作也较复杂,主要表现在以下四个方面: (1)在图结构中,每一个结点的地位都是相同的,没有一个“自然”的首结点,图中任意一个顶点都可作为访问的起始结点。 (2)在非连通图中,从一个顶点出发,只能够访问它所在的连通分量上的所有顶点,因此,还需考虑如何访问图中
18、其余的连通分量。 (3)在图结构中,如果有回路存在,那么一个顶点被访问之后,有可能沿回路又回到该顶点。 (4)在图中,一个顶点可以和其它多个顶点相连,当这个顶点访问过后,就要考虑如何选取下一个要访问的顶点。,7-3-1 深度优先搜索 深度优先搜索(Depth-Fisrst Search)遍历类似于树的先根遍历,是树的先根遍历的推广。 假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点发v出发,首先访问此顶点,然后任选一个v的未被访问的邻接点w出发,继续进行深度优先搜索,直到图中所有和v路径相通的顶点都被访问到;若此时图中还有顶点未被访问到,则另选一个未被访问的顶点作为起始点,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 数据结构 06
链接地址:https://www.31doc.com/p-3479463.html