《计算机软件技术基础 教学课件 ppt 作者 李淑芬 第5章》由会员分享，可在线阅读，更多相关《计算机软件技术基础 教学课件 ppt 作者 李淑芬 第5章（43页珍藏版）》请在金锄头文库上搜索。
1、第5章 图,5.1 图的定义,图是一种由一个顶点集 V 和一个弧集 V R构成的数据结构。 Graph = (V , V R ) 其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。 谓词 P(v,w) 定义了弧 的意义或信息。,图的结构定义,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。,E,A,C,B,D,例如:,G1 = (V1, VR1),其中 V1=A, B, C, D, E VR1=, , , , , , ,若VR 必有VR, 则用(v,w) 表示顶点v 与顶点 w 之间存在一条边。,B,C,A,F,E,D,由顶点集和
2、边集构成的图称作无向图。,例如: G2=(V2,VR2) V2=A, B, C, D, E, F VR2=(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F) ,名词和术语,网、子图,完全图（n*(n-1)/2,n*(n-1)、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、 强连通图、强连通分量,A,B,E,C,F,设图G=(V,VR) 和图 G=(V,VR), 且 VV, VRVR, 则称 G 为 G 的子图。,15,9,7,21,11,3,2,弧或边带权的图分别称作有向网或无向网。,假设图中有 n 个
3、顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图；含有 e=n(n-1) 条弧的有向图称作有向完全图；若图的边或弧的数目接近于相应完全图的边或弧的数目，则称之为稠密图，否则称为稀疏图。,在无向图中，假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，边(v,w) 和顶点v 和w 相关联。与顶点v 关联的边的条数称为顶点v的度。,A,C,D,F,E,例如:,ID(B) = 3,ID(A) = 2,B,顶点的出度: 以顶点v为弧尾的弧的数目；顶点的入度: 以顶点v为弧头的弧的数目。 顶点的度(TD)= 出度(OD)+入度(ID),A,B,E,C,F,有向图,例如
4、:,ID(B) = 2,OD(B) = 1,TD(B) = 3,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。,例如:A,B,C,F的路径长度为3。,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的简单路径。,若图G中任意两个顶点之间都有路径相通，则称此图为连通图；,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,B,A,C,D,F,E,B,A,C,D,F,E,对于有向图， 若任意两个顶点之
5、间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则将由各个连通分量构成的生成树集合称做此非连通图的生成森林。,建立和销毁图结构,插入或删除顶点,对邻接点的操作,访问顶点,遍历图,插入和删除弧,基本操作,5.2 图的存储表示,图的存储表示,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,*三、有向图的十字链表存储表示,*四、无向图的邻接多重表存储表示,Aij=,0 (i,j)VR,1 (i,j)VR,
6、一、图的数组(邻接矩阵)存储表示,定义:矩阵的元素为,A,B,C,D,E,F,A,B,C,D,E,F,有向图的邻接矩阵为非对称矩阵,A,B,C,D,E,特点,无向图是对称矩阵; 有向图不一定是对称矩阵 判断任意两个点的邻接关系容易 适用于稠密图,二、图的邻接表存储表示,0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3,有向图的邻接表,在有向图的邻接表中不易找到指向该顶点的弧，即难以确定某个顶点的入度。,有向图的逆邻接表,在有向图的逆邻接表中，每个顶点链接的是指向该顶点的弧。,弧的结点结构,顶点的结点结构,邻接表的定义,5.3 图的遍历,图的
7、遍历,从图中某个顶点出发访问图中每个顶点 一次且仅一次的过程。,深度优先搜索,广度优先搜索,从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点，直至图中所有和V0有路径相通的顶点都被访问到为止。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历(用栈),W1、W2和W3 均为 V0 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V0 ： for (W1、W2、W3 ) 若该邻接点Wi未被访问过， 则从它出发进行深度优先搜索遍历。,算法分析,1. 深度优先搜索遍历连通图的过程类似于树的先根遍历；,
8、解决的办法：设立一个一维数组，用来记录每个顶点是否被访问过，即 “访问标志 visitedw”。,2. 如何判别V0的邻接点是否被访问？,首先将图中每个顶点的访问标志设为 FALSE, 随后搜索图中每个顶点，如果未被访问过，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一个顶点。,非连通图的深度优先搜索遍历,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,访问标志:,访问次序:,例如:,0 1 2 3 4 5 6 7 8,0,1,6,2,3,4,5,7,8,二、广度优先搜索遍历图,对连通图，从起始点v到其余各顶点必定存在路径
9、。,其中，vw1, v w2, v w8 的路径长度为1；,v w7, v w3, v w5 的路径长度为2；,v w6, v w4 的路径长度为3。,从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，随后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有与V0有路径相通的顶点都被访问到为止。,连通图的广度优先搜索遍历(用队),若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,非连通图的广度优先搜索遍历,5.4 两顶点之间的最短路径,两点之间的最短路径问题,求从某个源点到其余各顶点的最短
10、路径,每一对顶点之间的最短路径(略),求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径。,源点,v1,其中，从源点到顶点v的最短路径是指从源点到v的所有路径中权值之和最小的那条路径。,v2,v1 :无 v0v2:10 v0 v4 v3:50 v0 v4:30 v0 v4 v3 v5:60,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的路径为：,路径长度上第一条最短路径为：,它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。,其余最短路径的特点：,再下一条路径长度次
11、短的路径为:,可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。,求最短路径的迪杰斯特拉算法：,一般情况下， Dk = 或者 = + 。,设置辅助数组D，其中每个分量Dk 表示当前所求得的从源点到顶点 k 的最短路径。,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的Dk值。 假设求得最短路径的顶点为u， 若 Du+G.arcsukDk 则将 Dk 改为 Du+G.arcsuk。,V0和k之间存在弧,V0和k之间不存在弧,其中的最小值即为最短路径的长度。,v0,v1,v2,v3,v4,v5,100,60,30,20,10,50,5,10,v0 v1 v2 v3 v4 v5,v0,10,30,100,v2,10,60,v4,30,50,90,v3,50,60,v5,60,D:,
