《数据结构（C语言版）》电子教案－赵坚 数据结构07

《《数据结构（C语言版）》电子教案－赵坚 数据结构07》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》电子教案－赵坚 数据结构07（118页珍藏版）》请在金锄头文库上搜索。

1、2019/5/25,1,第7章 图,本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的： 教学重点：图的各种存储方式及其运算 教学难点：图结构存储方式的选择，几种经典图算法的实现 本章内容：图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,2019/5/25,2,本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该： 1) 了解图的定义和术语 2) 掌握图的各种存储结构 3) 掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法,本章学习导读,2019/5/25,3,

2、图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。 在线性结构中，结点之间的关系是线性关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。 在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。 由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科

3、学以及数学的其它分支中。,2019/5/25,4,7. 1 .1 图的定义 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) V = x | x 某个数据对象 ， 是顶点的有穷非空集合； R边的有限集合 R = (x, y) | x, y V 无向图 或 R = | x, y V & Path (x, y)有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。x弧尾，y弧头。,7.1 图及其基本运算,2019/5/25,5,有向图与无向图 有向图中：边用表示，且x与y是有序的。

4、a. 有向图中的边称为“弧” b. x弧尾或初始点 y弧头或终端点 无向图：边用(x, y) 表示，且顶x与 y是无序的。 完全图 在具有n 个顶点的有向图中，最大弧数为 n(n-1) 在具有n 个顶点的无向图中，最大边数为 n(n-1)/2 顶点的度 无向图：与该顶点相关的边的数目 有向图： 入度ID(v) ：以该顶点为头的弧的数目 出度OD(v) ：以该顶点为尾头的弧的数目 在有向图中, 顶点的度等于该顶点的入度与出度之和。,2019/5/25,6,图7-1 无向图和有向图,2019/5/25,7,在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为： V(G1)=1，2，3，

5、4，5，6，7， E(G1)=(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)。 图(c)为有向图，其中G3的顶点集合和弧集合分别为 V(G3)=1，2，3，4，5，6， E(G3)=，,2019/5/25,8,7.1.2 图的基本术语 1 顶点的度 与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。 例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。 例如在图7-1中，有向图G3中顶点1的出度OD (1)=3，入度ID (

6、1)=1，其度TD (1)=4。,2019/5/25,9,2路径和回路 在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。 若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。 起点和终点相同的路径称为回路； 简单路径组成的回路称为简单回路。 路径长度 路径上经过的边的数目称为该路径的路径长度。 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和。,2019/5/25,10,简单路径 若路径上各顶点 v1

7、,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。,2019/5/25,11,3.边和弧 边: 无向图中顶点的偶对，写成（Vx，Vy）或（Vy，Vx）。 弧: 有向图中顶点的偶对,Vx,Vy表示从Vx到Vy。 弧头: 弧的终点 弧尾: 弧的起点,弧 Vx，Vy 弧尾Vx 弧头Vy,2019/5/25,12,4子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,2019/5/25,13,图7-3 连通分量和强连通分量,5连通性 在无向图中,

8、若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点vi和vj（vi，vjV）都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 图7-1中G1是连通图，G2是非连通图。 G2中有3个连通分量，如图7-3（a）所示。 6 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,2019/5/25,14,7网络 权 某些图的边或弧具有与它相关的数, 称之为权。权可以代表一个顶点到另一个顶点的距离，耗费等。 网络 这种带权连通图图一般

9、称为网络。如图7-4所示。,2019/5/25,15,8生成树、生成森林 生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。 生成树是对连通图而言的 是连同图的极小连同子图 包含图中的所有顶点 有且仅有n-1条边 非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,2019/5/25,16,9邻接点 顶点: 图中的结点 邻接点: 无向图中，若边(x,y)E， 两顶点之间有条边，则两顶点互 为邻接点。 x y ( x ,y ) 有向图中，若弧(x,y)E， 从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点。 x y

10、 ,2019/5/25,17,7.1.3 图的基本运算 图的基本运算也包括查找、插入和删除。 （1）顶点定位运算 确定顶点v在图中的位置； （2）取顶点运算 求取图中第i个顶点； （3）求第一个邻接点运算 求图中顶点v的第一个邻接点； （4）求下一个邻接点运算 已知w为图中顶点v的某个邻接点，求顶点w的下一个邻接点； （5）插入顶点运算 在图中增添一个顶点v作为图的第n+1个顶点，其中n为插入该顶点前图的顶点个数； （6）插入弧运算 在图中增添一条从顶点v到顶点w的弧。 （7）删除顶点运算 从图中删除顶点v以及所有与顶点v相关联的弧。 （8）删除弧运算 从图中删除一条从顶点v到顶点w的弧。,2

11、019/5/25,18,7.2 图的存储结构,无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。 在有向图中： 第 i 行 1 的个数就是顶点 i 的出度， 第 j 列 1 的个数就是顶点 j 的入度。 在无向图中, 第 i 行 (列) 1 的个数就是顶点i 的度。,2019/5/25,19,图7-6 有向图及其邻接矩阵,图7-5 无向图及其邻接矩阵,2019/5/25,20,对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。 无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。 对有向图，弧和表示方向不同

12、的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。 邻接矩阵表示法适合于以顶点为主的运算。,2019/5/25,21,对于有向图，顶点vi的出度OD (vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID (vi)等于邻接矩阵第i列元素之和，即 ：,对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：,OD (vi)=,ID (vi)=,TD（vi）=,对于带权图的邻接矩阵，定义为：,2019/5/25,22,顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。 使用邻接矩阵存储结构，可用一维数组表示图的顶点集合

13、，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下： #define MAX_VERTEX_NUM 20 /最大顶点数 typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵类型 typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点表 AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /图的顶点数和弧数 MGraph; 由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。,2019/5/25,23,建立邻

14、接矩阵算法: void CreateMGraph(MGraph ,j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; return; ,2019/5/25,24,void PrintMGraph(MGraph G) /输出 int i,j; printf(“Output Vertices:“); printf(“%s“,G.vexs); printf(“n“); printf(“Output AdjMatrix:n“); for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) printf(“%4d“,G.arcsij);

15、printf(“n“); return; ,2019/5/25,25,7.2.2 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表， 2) 第i个单链表中包含顶点Vi的所有邻接顶点。 邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。,2019/5/25,26,把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域adjvex保存与该边相关联的另一顶点的顶点下标 ， 链域nextarc存放指向同一链表中下一个表结点的指针 ，数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储，其数据域data存放顶点信息，链域firstarc指向链表中第一个顶点。,2019/5/25,27,带权图的边结点中info保存该边上的权值 。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。 在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输