华师本科生数据结构课件 第7章 图.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《华师本科生数据结构课件 第7章 图.ppt》由会员分享,可在线阅读,更多相关《华师本科生数据结构课件 第7章 图.ppt(134页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1,2,图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,即每个数据元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素 之间有着明显的层次关系,虽然每一层上的数据元素可能和下一层中多个元素(孩子) 相关,但只能和上一层中一个元素(双亲)相关;而在图形结构中,结点之间 的关系可以是任意的,任意两个数据元素之间都可能相关。 图在各个领域都有着广泛的应用,如电路网络分析、交通运输、管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题,它们必须用图的有关方法进行处理;另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多
2、实际问题,如果间接地用图来表示,处理起来比较方便。这些技术领域都是把图作为解决问题的主要数学手段来使用,因此,如何在计算机中表示和处理图结构,就是计算机科学需研究的一项重要课题。,3,【学习目标】,1领会图的类型定义.2熟悉图的各种存储结构及其构造算法, 了解各种存储结构的特点和选用原则.3熟练掌握图的两种遍历算法.4理解各种图的应用问题的算法. 5.了解广义表的结构和使用,4,【重点和难点】,图的应用极为广泛,而且图的各种应用问题的算法都比较经典,因此本章重点在于理解各种图的算法及其应用场合。,【知识点】,图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生
3、成树、最短路径、拓扑排序、关键路径,5,第七章 习题,基础知识 P47:7.1 7.5 7.7 7.9 7.10 7.11 作业 P49:7.22 7.23 7.24 7.28 7.32 P50:7.36 7.41,6,7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 连通网的最小生成树 7.5 单源最短路径 7.6 拓扑排序 7.7 关键路径 7.8 广义表,第7章 图和广义表,7,7.1 图的基本术语,图:记为 G( V, E ) 其中:V 是G的顶点集合,是有穷非空集; E 是G的边集合,是有穷集。,问:当E(G)为空时,图G存在否? 答:还存在!但此时图G只有顶点
4、而没有边。,有向图: 无向图: 完全图:,图G中的每条边都是有方向的; 图G中的每条边都是无方向的; 图G任意两个顶点都有一条边相连接;,若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图,V=vertex E=edge,8, 完全有向图有n(n-1)条边。 证明:若是完全有向图,则顶点1必必与所有其他顶点各有2条连线,即有2(n-1)条边, 顶点2有2(n-2)条边,顶点n-1有2条边,顶点n有0条边. 总边数2( n-1 n-210)=2(n-1+0)n/2= n(n-1),完全无向图有n(n-1)/2 条边。
5、证明:若是完全无向图,则顶点1必与所有其他顶点各有1条连线,即有n-1条边,顶点2有n-2条边,顶点n-1有1条边,顶点n有0条边. 总边数 n-1 n-210=(n-1+0)n/2= n(n-1)/2,9,例:判断下列4种图形各属什么类型?,无向,无向图(树),有向图,有向,n(n-1)/2 条边,n(n-1) 条边,G1的顶点集合为V(G1)=0,1,2,3 边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,10,图G1中:V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,图G2中:V(G2)=1,2,3,4
6、,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),11,稀疏图:稠密图:,设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。,子 图:,边较少的图。通常边数n2 边很多的图。无向图中,边数接近n(n-1)/2 ; 有向图中,边数接近n(n-1),12,带权图:,即边上带权的图。其中权是指每条边可以标上具有某种含义的数值(即与边相关的数)。,连通图:,在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图
7、。 非连通图的极大连通子图叫做连通分量。,带权图,在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。,强连通图:,网 络:,有两类图形不在本课程讨论之列:,13,邻接点:,有向边(u, v)称为弧,边的始点u叫弧尾,终点v叫弧头,顶点v的度是与它相关联的边的条数。记作D(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。,若 (u, v) 是 E
8、(G) 中的一条边,则称 u 与 v 互为邻接顶点,弧头和弧尾:,度、入度和出度:,生成树:,是一个极小连通子图,它含有图中全部顶点,但只有n-1条边。 如果在生成树上添加1条边,必定构成一个环。 若图中有n个顶点,却少于n-1条边,必为非连通图。,生成森林:,问:当有向图中仅1个顶点的入度为0,其余顶点的入度均为1,此时是何形状?,由若干棵生成树组成,含全部顶点,但构成这些树的边是最少的。,答:是树!而且是一棵有向树!,14,简单路径:,路径上各顶点 v1,v2,.,vm 均不互相重复。,回 路:,例:,若路径上第一个顶点 v1 与最后一个顶点vm 重合,则称这样的路径为回路或环。,路径:,
9、在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm,到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于E的边。,路径长度:,非带权图的路径长度是指此路径上边的条数; 带权图的路径长度是指路径上各边的权之和。,15,16,路径:1,2,3,5,6,3 路径长度:5 简单路径:1,2,3,5 回路:1,2,3,5,6,3,1 简单回路:3,5,6,3,路径:1,2,5,7,6,5,2,3 路径长度:7
10、 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2,1 简单回路:1,2,3,1,17,连通图,强连通图,非连通图 连通分量,18,CreatGraph( /从顶点v起广度优先遍历图G,并对每个顶点调用Visit一次。,结构的建立和销毁 对顶点的访问操作 插入或删除顶点 插入和删除 对邻接点的操作 遍历,基本操作,19,7.2 图的存储结构,图的特点:非线性结构(m :n ),邻接表 邻接多重表 十字链表,设计为邻接矩阵,链式存储结构:,顺序存储结构:,无!,(多个顶点,无序可言) 但可用数组描述元素间关系。,可用多重链表,重点介绍:,邻接矩阵(数组)表示法 邻接表(链式)表示法
11、,20,一、邻接矩阵(数组)表示法,建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间关系)。 设图 A = (V, E) 有 n 个顶点,则图的邻接矩阵是一个二维数组 A.Edgenn,定义为:,例:,邻接矩阵:,A.Edge =,( v1 v2 v3 v4 v5 ),v1 v2 v3 v4 v5,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,分析1:无向图的邻接矩阵是对称的; 分析2:顶点i 的度第 i 行 (列) 中1 的个数; 特别:完全图的邻接矩阵中,对角元素为0,其余全1。,0 1 0 1 0 1 0 1 0 1
12、 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,顶点表:,21,例 :有向图的邻接矩阵,分析1:有向图的邻接矩阵可能是不对称的。 分析2:顶点的出度=第i行元素之和,OD( Vi )= A.Edge i j 顶点的入度=第i列元素之和。ID( Vi )= A.Edge j i 顶点的度=第i行元素之和+第i列元素之和, 即:TD(Vi)=OD( Vi ) + ID( Vi ),邻接矩阵:,A.Edge =,( v1 v2 v3 v4 ),v1 v2 v3 v4,0 0 0 0 0
13、0 0 0 0 0 0 0 0 0 0 0,注:在有向图的邻接矩阵中, 第i行含义:以结点vi为尾的弧(即出度边); 第i列含义:以结点vi为头的弧(即入度边)。,顶点表:,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,22,容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,特别讨论 :网(即有权图)的邻接矩阵,定义为:,以有向网为例:,邻接矩阵:, ,N.Edge =,( v1 v2 v
14、3 v4 v5 v6 ),邻接矩阵法优点:,邻接矩阵法缺点:,顶点表:,5 7 4 8 9 5 6 5 3 1, 5 7 4 8 9 5 6 5 3 1 ,23,注:用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef enum DG, DN, AG,AN GraphKind; /有向/无向图,有向/无向网 Typedef struct ArcCell /弧(边)结点的定义 VRType adj; /顶点间关系,无权图取1或0;有权图取权值类型 InfoType *
15、info; /该弧相关信息的指针 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ; Typedef struct /图的定义 VertexType vexs MAX_VERTEX_NUM ; /顶点表,用一维向量即可 AdjMatrix arcs; /邻接矩阵 int vernum, arcnum; /顶点总数,弧(边)总数 GraphKind kind; /图的种类标志 Mgraph;,图的邻接矩阵存储表示,对于n个顶点的图或网,空间效率=O(n2),24,Status CreateUDN(Mgraph /CreateUDN,例:用邻接矩阵
16、生成无向网的算法,对于n个顶点e条弧的网, 建网时间效率 = O(n2+n+e*n),25,二、邻接表(链式)表示法,对每个顶点vi 建立一个单链表,把与vi有关联的边的信息(即度或出度边)链接起来,表中每个结点都设为3个域;,每个单链表还应当附设一个头结点(设为2个域),存vi信息;,表结点,头结点,邻接点域,表示vi一个邻接点的位置,链域,指向vi下一个边或弧的结点,数据域,与边有关信息(如权值),数据域,存储顶点vi 信息,链域,指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,26,例:无向图的邻接表,邻接表,例:有向图的邻接表,邻接表(出边),注:邻接表不唯一,因各
17、个边结点的链入顺序是任意的。,当邻接表的存储结构形成后,图便唯一确定!,27,分析1: 对于n个顶点e条边的无向图,邻接表中除了n个头结点外,只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2),则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点:,分析2: 在有向图中,邻接表中除了n个头结点外,只有e个表结点,空间效率为O(n+e)。若是稀疏图,则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度?,邻接表的缺点:,怎样计算有向图顶点的出度? 怎样计算有向图顶点的入度? 怎样计算有向图顶点Vi的度:,需遍历全表,邻接表的优点:,TD( Vi )
18、=单链表中链接的结点个数,OD( Vi )单链出边表中链接的结点数 I D( Vi ) 邻接点为Vi的弧个数,TD( Vi ) = OD( Vi ) + I D( Vi ),空间效率高;容易寻找顶点的邻接点;,判断两顶点间是否有边或弧,需搜索两结点对应的单链表,没有邻接矩阵方便。,28,讨论:邻接表与邻接矩阵有什么异同之处?,联系:邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数。 区别: 对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)
19、。 用途:邻接矩阵多用于稠密图的存储(e接近n(n-1)/2);而邻接表多用于稀疏图的存储(en2),29,图的邻接表存储表示,#define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef struct ArcNode int adjvex; /该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针 ArcNode; Typedef struct VNode /顶点结构 VertexType data; /顶点信息 ArcNode * firstarc; /指向依附该顶点的第一
20、条弧的指针 VNode, AdjList MAX_VERTEX_NUM ; Typedef struct /图结构 AdjList vertics ; /应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数 int kind; /还应说明图的种类(用标志) ALGraph; /图结构,空间效率为O(n+2e)或O(n+e) 时间效率为O(n+e*n),30,void CreateUDG(ALGraph /for / CreateUDG,31,一、深度优先搜索 二、广度优先搜索,7.3 图的遍历,遍历定义:从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使
21、每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算。,遍历实质:找每个顶点的邻接点的过程。 图的特点:图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,解决思路:可设置一个辅助数组 visited n ,用来标记每个被访问过的顶点。它的初始状态为0,在图的遍历过程中,一旦某一个顶点i 被访问,就立即改 visited i为1,防止它被多次访问。,图常用的遍历:,怎样避免重复访问?,32,深度优先搜索(DFS),V2,V4,V8,V5,V3,V6,V7,生成树 遍历序列,广度优先搜索(BFS),V2,V3,V4,V5,V6,
22、V7,V8,最短路径!,图的遍历-例子,33,一、深度优先搜索( DFS ),基本思想:仿树的先序遍历过程。,Depth_First Search,v1,DFS 结果,例1:,v2,v4,v8,v5,v3,v6,v7,例2:,v2 v1 v3 v5 ,DFS 结果,v4 v6,起点,起点,遍历步骤,1、深度优先搜索: 有向图的实例:为了说明问题,邻接结点的访问次序以序号为准。序号小的先访问。 如:结点5的邻接结点有两个6、7,则先访问结点6,再访问结点7。,5,6,7,2,4,1,3,5,6,7,2,3,1,4,从结点 出发的搜索序列: 5、6、2、3、1、4、7 适用的数据结构:栈,5,1,
23、2,4,3,从结点 出发的搜索序列: 1、2、3、4没有搜索 到所有的结点,必 须另选图中未访 问过的结点, 继续进行 搜索。,1,35,一、深度优先搜索遍历图,连通图的深度优先搜索遍历:从图中某个顶点V0 出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V0有路径相通的顶点都被访问到。,W1、W2和W3 均为 V 的邻接点,SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V ; for (W1、W2、W3 ) 若该邻接点W未被访问, 则从它出发进行深度优先搜索遍历。,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华师本科生数据结构课件 第7章 本科生 数据结构 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内