数据结构第16次课图A.ppt

《数据结构第16次课图A.ppt》由会员分享，可在线阅读，更多相关《数据结构第16次课图A.ppt（46页珍藏版）》请在装配图网上搜索。

1、第1页,上课定律 大一：你怎么迟到了？ 大二：你今天怎么没上课？ 大三：你上课去吗？ 大四：你怎么上课去了？ 考试定律 大一：什么!明天要考微积分！？ 大二：什么!等下要考微积分！？ 大三：什么!刚刚考的是微积分！？ 大四：什么！微积分什么时候考的！？,每课一贴：,大家可不能如此蜕变啊！,第2页,数据结构课程的内容,多对多 （m:n),第3页,7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的其他运算 7.5 图的应用,第7章 图,第4页,7.1 图的基本术语,图：记为 G( V, E ) 其中：V 是G的顶点集合，是有穷非空集； E 是G的边集合，是有穷集。,问：当E(G)为

2、空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。,有向图： 无向图： 完全图：,图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接；,若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图,V=vertex E=edge,第5页,证明：, 完全有向图有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)

3、n/2= n(n-1),完全无向图有n(n-1)/2 条边。 证明：若是完全无向图，则顶点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,第6页,例：判断下列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),完全图,完全图,第7页,稀疏图：边较少的图。通常边数n2,子 图：设有两个图

4、 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。,稠密图：边很多的图。无向图中，边数接近n(n-1)/2 ； 有向图中，边数接近n(n-1),带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。,网 络： 带权图,第8页,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复。,回 路：,例：,若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。,路径：,在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点vj。则称顶点序

5、列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。,第9页,路径：1，2，3，5，6，3 路径长度：5(路径上结点数-1) 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1,第10页,弧头和弧

6、尾：有向边(u, v)称为弧，边的始点u叫弧尾，终点v叫弧头,顶点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。,邻接顶点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点,度、入度和出度：,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,答：是树！而且是一棵有向树！,第11页,生成树：,是一个极小连通子图，它含有图中全部顶点，但只有 n-1条边。 如果

7、在生成树上添加1条边，必定构成一个环。 若图中有n个顶点，却少于n-1条边，必为非连通图。,第12页,连 通 图：,在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。,在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。,强连通图：,有两类图形不在本章讨论之列：,第13页,ADT Graph 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R=VR；VR=|v,wV 且 P(v,w), 表示从v到w的弧， 谓词P(v,w)定义了弧的意义或

8、信息 基本操作P： CreatGraph ( 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中添加新顶点。 （参见P156-257） ,图的抽象数据类型,注意：V 的大小写含义不同！,第14页,7.2 图的存储结构,图的特点：非线性结构（m :n ）,邻接表 邻接多重表 十字链表,设计为邻接矩阵,链式存储结构：,顺序存储结构：,无！,（多个顶点，无序可言） 但可用数组描述元素间关系。,可用多重链表,重点介绍：,邻接矩阵(数组)表示法 邻接表(链式)表示法,第15页,一、邻接矩阵（数组）表示法,建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。 设图 A

9、= (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgenn，定义为：,例1：,邻接矩阵：,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 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

10、 1 0 1 0 1 0 1 1 1 0,顶点表：,第16页,例2 ：有向图的邻接矩阵,分析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 0 0 0 0 0 0 0 0 0 0 0,注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）

11、； 第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,第17页,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。,特别讨论 ：网（即有权图）的邻接矩阵,定义为：,以有向网为例：,邻接矩阵：, ,N.Edge =,( v1 v2 v3 v4 v5 v6 ),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5 7 4 8 9 5 6 5 3 1

12、, 5 7 4 8 9 5 6 5 3 1 ,第18页,注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef enum DG, DN, AG,AN GraphKind; /有向/无向图，有向/无向网 Typedef struct ArcCell /弧（边）结点的定义 VRType adj; /顶点间关系，无权图取1或0；有权图取权值类型 InfoType *info; /该弧相关信息的指针 ArcCell, AdjMatrix MAX_VERTEX_NUM MA

13、X_VERTEX_NUM ;,图的邻接矩阵存储表示（参见教材P161）,对于n个顶点的图或网，空间效率=O(n2),第19页,Typedef struct /图的定义 VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可 AdjMatrix arcs; /邻接矩阵 Int Vernum, arcnum; /顶点总数，弧（边）总数 GraphKind kind; /图的种类标志 Mgraph;,第20页,二、邻接表（链式）表示法,对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域；,每个单链表还应当附设

14、一个头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi一个邻接点的位置,链域，指向vi下一个边或弧的结点,数据域，与边有关信息（如权值）,数据域，存储顶点vi 信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,第21页,例1：无向图的邻接表,邻接表,例2：有向图的邻接表,邻接表(出边),逆邻接表(入边),注：邻接表不唯一，因各个边结点的链入顺序是任意的。,第22页,例3：已知某网的邻接（出边）表，请画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,第23页,分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结

15、点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,怎样计算有向图顶点的出度？ 怎样计算有向图顶点的入度？ 怎样计算有向图顶点Vi的度：,需遍历全表,邻接表的优点：,TD(Vi)=单链表中链接的结点个数,OD(Vi)单链出边表中链接的结点数 I D( Vi ) 邻接点为Vi的弧个数,TD(Vi) = OD( Vi )

16、+ I D( Vi ),空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,第24页,讨论：邻接表与邻接矩阵有什么异同之处？,1. 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 2. 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。(考试怎么办？给定顺序） 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 3. 用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),第

17、25页,图的邻接表存储表示（参见教材P163）,#define MAX_VERTEX_NUM 20 /假设的最大顶点数 Typedef struct ArcNode int adjvex; /该弧所指向的顶点位置 struct ArcNode *nextarcs; /指向下一条弧的指针 InfoArc *info; /该弧相关信息的指针 ArcNode； Typedef struct VNode /顶点结构 VertexType data; /顶点信息 ArcNode * firstarc; /指向依附该顶点的第一条弧的指针 VNode, AdjList MAX_VERTEX_NUM ; Ty

18、pedef struct /图结构 AdjList vertics ; /应包含邻接表 int vexnum, arcnum; /应包含顶点总数和弧总数 int kind; /还应说明图的种类（用标志） ALGraph; /图结构,图的邻接表生成算法作为自测题。,空间效率为O(n+2e)或O(n+e) 时间效率为O(n+e*n),第26页,一、深度优先搜索 二、广度优先搜索,7.3 图的遍历,遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。,遍历实质：找每个顶点的邻接点的过程。 图的遍历操作的特点：图中可能存在回

19、路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,解决思路：可设置一个辅助数组 visited n ，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。,图常用的遍历：,怎样避免重复访问？,第27页,一、深度优先搜索( DFS ),基本思想：仿树的先序遍历过程。,Depth_First Search,v1,DFS 结果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5 ,DFS 结果,v4 v6,起点,起点,遍历步骤,

20、第28页,深度优先搜索（遍历）步骤：,详细归纳： 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1； 再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2； 然后再从 w2 出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。 若有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问； 若没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,简单归纳： 访问起始点 v; 若v的第1个邻接点没访问过，深度遍历此邻接点；

21、若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,第29页,深度遍历：V1 V2 V4 V8 V5 V6 V3 V7,深度遍历：V1 V2 V4 V8 V3 V6 V7 V5,深度遍历：V1 V2 V4 V3 V5 V6,练习：,第30页,讨论1：计算机如何实现DFS？,DFS 结果,邻接矩阵 A,辅助数组 visited n ,起点,v2v1v3v5v4v6,开辅助数组 visited n！,例：,第31页,讨论2：DFS算法如何编程？,DFS1(A, n, v) visit（v）; visitedv=1; for( j=1; j=n; j+) if ( Av, j ,可以用递归算法！,

22、/Ann为邻接矩阵，v为起始顶点(编号）,/访问（例如打印）顶点v,/ DFS1,Av,j 1 有邻接点,visited n =0 未访问过,/访问后立即修改辅助数组标志,/从v所在行从头搜索邻接点,（严教材上DFS递归算法见P169）,第32页,深度优先遍历算法流程图,第33页,讨论3：在图的邻接表中如何进行DFS？,v0 v1 v2 v3,DFS 结果,辅助数组 visited n ,例：,照样借用visited n ！,起点,0 1 2 3,注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。,第34页,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V

23、4,第35页,讨论4： 邻接表的DFS算法如何编程？,仍可用递归算法,DFS2(List, v, p) visit（v）; visitedv=1; p=p-link; while (!p) v=p-data; if(! visitedv ) DFS2(list, v, p); p=p-link; ,第36页,DFS 算法效率分析:,（设图中有 n 个顶点，e 条边） 如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。 如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图

24、的时间复杂度为O(n+e)。,结论： 稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。,第37页,二、广度优先搜索( BFS ),基本思想：仿树的层次遍历过程。,Breadth_First Search,v1,BFS 结果,例1：,例2：,v3 ,BFS 结果,v4 v5 ,起点,遍历步骤,起点,v2 v1 v6 ,v9 v8 v7,第38页,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,广度遍历：V1 V2 V3 V4 V6 V7 V8 V5,练习：,第39页,广度优先搜索（遍历）步骤：,简单归纳：

25、 在访问了起始点v之后，依次访问 v的邻接点； 然后再依次访问这些顶点中未被访问过的邻接点； 直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,第40页,讨论1：计算机如何实现BFS？,邻接表,除辅助数组visited n 外，还需再开一辅助队列！,例：,起点,辅助队列,v2已访问过了,BFS 遍历结果,入队！,初始f=n-1,r=0,第41页,讨论2： BFS算法如何编程？,BFS1(List, n, v) Visit(v); Visitedv=1; fr

26、ont=n-1;rear=0; qrear=v; while(rear!=front) front=(front+1)%n; v=qfront; p=Listv.firstarc; while(!p) if(! Visitedadjvex(p) ) Visit(adjvex(p); Visitedadjvex(p)=1; rear=(rear+1)%n; qrear= adjvex(p) p=nextarc(p); return; ,层次遍历应当用队列！,/List为邻接表，v为起点，Qn为辅助队列,/访问（例如打印）顶点v并修改标志,/ BFS1,/指向单链表中下一个邻接点,/队列指针初始化

27、,/起始点入队,/队不空时,/访问过的顶点出队,/P指向第1个邻接点,未到表尾，且邻接域未访问过，,则先输出再改标记，最后再入队,第42页,第43页,广度优先遍历算法,Ch6_2.c,第44页,BFS 算法效率分析:,DFS与BFS之比较： 空间复杂度相同，都是O(n)(借用了堆栈或队列）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFS循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。,（设图中有 n 个顶点，e 条边）,第45页,void AJ(adjlist GL,int i,int n) Queue Q; InitQueue(Q); coutadjvex; if (!visitedj),coutnext; ,该函数实现的是( )的( )操作，其中采用的存储结构是( ), 调用了( )数据结构?,第46页,void AK(adjlist GL,int i,int n) coutadjvex; if( ! visitedj ) AK(GL,j,n); p=p-next; ,该函数实现的是( )的( )操作，系统内部需要调用( )数据结构?,