《数据结构7图.ppt》由会员分享，可在线阅读，更多相关《数据结构7图.ppt（40页珍藏版）》请在三一办公上搜索。
1、第七章.图（Chapter 7.Graph),7.1 图的定义及基本操作,图型结构是一种非常重要的、比线性和树型结构更复杂的非线性数据结构，可广泛用于描述自然界各种关系。,右图所示即为一图型结构：,图的一些基本术语：,顶点（vertex）,数据元素所构成的结点通常称为顶点。,弧（arc）,若两个顶点间有关系 E，则称 为一条弧。,弧头（head-又称终端点 terminal node）,若 为一条弧，则顶点 y 称为弧头。,弧尾（tail-又称初始点 initial node）,若 为一条弧，则顶点 x 称为弧尾。,有向图（directed graph）,若 E，并不总有 E，则称此图为有向图
2、。,无向图（undirected graph）,若 E，总有 E，则称此图为无向图。,边（edge）,无向图中两条弧和可用一条边（x,y）来表示。,完全图（completed graph）,具有 n*(n-1)/2 条边的无向图称为完全图。,有向完全图（completed directed graph）,具有 n*(n-1)条弧的有向图称为有向完全图。,稀疏图（sparse graph）,边数很少的图称为稀疏图。,权（weight）,有些图的边或弧具有一定的大小，称之为权。,网（network）,带权值的图又称为网或网络。,子图（subgraph）,由图的部分顶点和边组成的新图称为原图的子图。
3、,生成子图（spanning subgraph）,由图的全部顶点和部分边组成的子图称为原图的生成子图。,稠密图（dense graph）,边数很多的图称为稠密图。,邻接点（adjacent）,若边（vi,vj）E，则 vi 与 vj 互为邻接点。,依附（incident）,若边（vi,vj）E，则称边（vi,vj）依附于顶点 vi 和 vj。,相关联（correlative）,若边（vi,vj）E，又称边（vi,vj）与顶点 vi 和 vj 相关联。,顶点的度（degree）,与顶点相关联的边数称为该顶点的度，又分为入度和出度。,顶点的入度（indegree）,以顶点为头的弧数称为该顶点的入度
4、。,顶点的出度（outdegree）,以顶点为尾的弧数称为该顶点的出度。,路径（path）,由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。,回路（loop-又称环 cycle）,起点和终点为同一顶点的路径称为回路。,连通（connected）,无向图中顶点vi到vj间有路径存在，则称vi和vj是连通的。,连通图（connected graph）,无向图中任意两顶点间均存在路径，则称该图为连通图。,连通分量（connected component）,无向图中的极大连通子图称为原图的连通分量。,强连通图（strongly connected graph）,有向图中任意两顶点间均存在路径
5、，则称该图为强连通图。,强连通分量（strongly connected component）,有向图中的极大强连通子图称为原图的强连通分量。,生成树（spanning tree）,连通图的极小连通生成子图称为原图的生成树。,有向树（directed tree）,恰有一个顶点入度为0，其余顶点入度均为1的有向图。,生成森林（spanning forest）,由多棵有向树构成的有向图的生成子图称为生成森林。,最小代价生成树（minimum cost spanning tree）,连通网中由最小权值的边构成的生成树。,图的基本操作：,INITIATE,GETVERTEX,FIRSTADJ,NEXT
6、ADJ,INSVERTEX,TRAVERSE,INSARC,DELVERTEX,DELARC,7.2 图的存储结构,顺序存储结构：,1、邻接矩阵（adjacency matrix),CONST vtxnum=user_supply;TYPE vtx=1.vtxnum;bit=0.1;graph=ARRAY vtx,vtx OF bit;,2、关联矩阵（correlated matrix),CONST vtxnum=user_supply;edgenum=user_supply;TYPE vtx=1.vtxnum;edge=1.edgenum;bit=-1.1;graph=ARRAY vtx,e
7、dge OF bit;,链式存储结构：,1、邻接表（adjacency list),按结点出度建立：,TYPE arcptr=arcnode;vexnode=RECORD vexdata:vextype;firstarc:arcptr END;arcnode=RECORD adjvex:vtx;info:edgetype;nextarc:arcptr END;adjlist=ARRAY vtx OF vexnode;,2、逆邻接表（inverse adjacency list),按结点入度建立：,定义同邻接表,3、十字链表（orthogonal list),按结点入度和出度建立：,TYPE a
8、rclk=anode;vnode=RECORD data:vextype;firstin,firstout:arclk END;anode=RECORD tailvex,headvex:vtx;hlink,tlink:arclk END;ortholist=ARRAY vtx OF vnode;,4、邻接多重表（adjacency multilist),邻接多重表是无向图的一种存储结构：,TYPE edgelk=enode;vnode=RECORD data:vextype;firstedge:arclk END;enode=RECORD mark:0.1;ivex,jvex:vtx;ilin
9、k,jlink:edgelk END;adjmulist=ARRAYvtx OF vnode;,7.3 图的遍历,深度优先遍历（depth_first search）,即按某种搜索顺序对图中每个结点访问且仅访问一次。,从图中某一顶点 v0 出发，访问该顶点，并依次从v0的所有未被访问过的邻接点中任意选取一个顶点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0 连通的顶点均被访问到为止；若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点，反复此过程，直至图中所有顶点均被访问过一遍为止。,A,B,F,E,H,C,D,G,PROC Traverse(g:gra
10、ph;VAR visited:ARRAY vtx OF boolean);For v:=1 To vtxnum Do visited v:=false;For v:=1 To vtxnum Do If Not visitedv Then dfs(g,v)ENDP;,PROC dfs(g:graph;v:vtx);visit(v);visited v:=true;w:=FIRSTADJ(g,v);While w0 Do Begin If Not visited w Then dfs(g,w);w:=NEXTADJ(g,v,w)EndENDP;,广度优先遍历（breadth_first searc
11、h）,从图中某一顶点v0出发，访问该顶点，并依次访问v0的所有未被访问过的邻接点，然后将所有这些邻接点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0 连通的顶点均被访问到为止；若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点，反复此过程，直至图中所有顶点均被访问过一遍为止。,A,B,C,F,H,D,G,E,PROC Traverse(g:graph;Var visited:ARRAY vtx OF boolean);For v:=1 To vtxnum Do visited v:=false;For v:=1 To vtxnum Do If Not
12、visitedv Then bfs(g,v)ENDP;,PROC bfs(g:graph;v:vtx);visit(v);visited v:=true;INIQUEUE(Q);ENQUEUE(Q,v);While Not EMPTY(Q)Do Begin v:=DEQUEUE(Q);w:=FIRSTADJ(g,v);While w0 Do【If Not visited w Then【visit(w);visited w:=true;ENQUEUE(Q,w)】;w:=NEXTADJ(g,v,w)】EndENDP;,作 业20.自选存储结构，编写一算法判断无向图中任意给定的两个顶点间是否存在一条
13、长度为 k 的简单路径（即不含回路的路径）。21.自选存储结构，试给出求有向图中所有简单回路（即其中不再含有回路的回路）的算法。,7.4 图的连通性及最小代价生成树,无向图的连通分量：,一次调用深度或广度优先搜索（dfs、bfs）所得到的顶点集即为连通分量的顶点集。,有向图的强连通分量：,利用深度优先搜索遍历，从有向图中任意一个顶点出发遍历该图，记录每次递归退出 dfs 过程时的当前顶点序列；再按该序列逆序去逆向遍历该图（从弧头至弧尾），每调用一次 dfs 过程所得到的顶点集即为强连通分量的顶点集。,E,F,A,D,C,B,从 B 顶点出发正向遍历：,B,F,A,C,从 B 顶点出发逆向遍历：
14、,D,E,最小生成树：,一、Prim 算法：,1、将图中顶点分为两个集合，其中集合 X 包含图的一个顶点 v0，集合 Y 包含除 v0 外的其它所有顶点；,2、将跨接这两个集合的权值最小的边加入图中，并将其依附在集合 Y 中的顶点 v1 从 Y 中移入集合 X 中；,3、反复过程 2，直到集合 Y 为空，所得生成子图即为最小生成树。,二、Kruskal 算法：,1、将图中所有边按权值从小到大排序；,2、取权值最小的边，加入图中，判断是否形成了回路，若无，则保留此边，否则去掉该边，重取权值较小的边；,3、反复过程 2，直到全部顶点均连通为止。,三、破圈法：,1、在图中找到一个回路；,2、去掉该回
15、路中权值最大的边；,3、反复此过程，直到图中不存在回路为止。,四、去边法：,1、将图中所有边按权值从大到小排序；,2、去掉权值最大的边，若图不再连通则保留此边，再选取下一权值较大的边去掉；,3、反复此过程，直到图中只剩下 n-1 条边为止。,第 四 次 上 机 作 业 输入无向图的邻接矩阵，使用前面讲过的任意三种方法求该图的最小代价生成树，并分析各自的时间复杂度。,程序设计常用方法之三：贪心法（Greedy）,贪心法的特点是一步一步进行，根据某个优化测度（可能是目标函数），每一步都要保证获得局部最优解；每一步只考虑一个输入，它的选取应满足局部优化条件；若下一个输入与部分最优解一起不再是可行的解
16、，则不把该输入加到部分解中。反复此过程，直到得到问题的解或把所有输入枚举完为止。,我们可以先将单位价值最大的物体装入背包中，即将物体按 pi/wi 从大到小排序，有 p2/w2 p3/w3 p1/w1，则先将物体2全部装入，空余部分再装物体3，即得到最优解。,由此可见，贪心法是一种很直接的算法设计方法，用贪心法求问题的次优解效率是很高的。,设 n=3，M=20，pi=(25,24,15)，wi=(20,15,10)，则：,1、xi=(1/2,1/3,1/2)时有 pi xi=28；,2、xi=(1/5,1,1/10)时有 pi xi=305；,3、xi=(0,1,1/2)时有 pi xi=31
17、5；,显然第三个解较好（其实是最优解），但它是如何得到的呢？,4、xi=(1,0,0)时有 pi xi=25；,PROC Pack(n,M:integer;P,W:intArray;Var X:intArray);For i:=1 To n Do Xi:=0;i:=1;While(Wi M)And(i n)Do Begin Xi:=1;M:=M-Wi;i:=i+1 End;If i n Then Xi:=M/WiENDF;,有很多问题均可用贪心法求解，如求最小代价生成树的 Kruskal 算法。,上面的背包问题有时也描述成“0-1背包问题”，即 xi或者为 0 或者为 1，它也可先按单位价值从
18、大到小排序，再用上次作业的方法求解（第一个解即为次优解）即可。,7.5 有向无环图及其应用,无环的有向图称为有向无环图（directed acycline graph）。,拓扑排序（topological sort）,拓扑排序是指由集合上的一个偏序（partial order）得到该集合上的一个全序（total order）的过程。,由拓扑排序得到的全序又称为拓扑有序（topological order）。,一个表示偏序的有向图通常用来表示一个流程图。图中每条有向边分别表示两个子工程（活动）间的次序关系；而顶点则分别表示各活动，因此，这类图又称为顶点活动图（activity on vertex
19、 network），简称 AOV 图。,如用顶点表示课程，用弧表示某些课程是其它课程的先修课，则拓扑排序就是求在同时只能学习一门课程时的学习次序。,以下都是拓扑排序结果：,拓扑排序步骤：,1、扫描图中个顶点，将入度为零的顶点入队列；,若该有向图不是无环图，则不存在拓扑排序，就不可能输出全部顶点。此特点可用来判断一个有向图是否存在回路。,2、从队列中取出一个顶点输出，并将其所有邻接点的入度减一，若入度减为零，则将该邻接点入队列；,3、反复执行步骤 2，直至所有顶点的入度均为零。,关键路径（critical path）,关键路径是指影响整个工程进度的那些子工程（活动）所组成的路径。减少这些活动所需
20、时间，整个工程就能提前完成。,在这类有向无环图中，顶点一般用来表示事件（event），弧用来表示活动，权值表示活动所需时间，因此，此类有向无环图又称为边活动图（activity on edge network），简称AOE图。,如左图所示工程，其最后完工时间为21天。,能否加快某些活动进度，使整个工期缩短呢？,答案是肯定的。问题的关键是要提高哪些活动的效率才能缩短整个工期？这些活动就是我们要求的关键路径。,可用拓扑排序求的各事件（顶点）的最早发生时间，然后再用逆拓扑排序求的各事件的最晚发生时间，有：,设活动 a i=弧的权定义为活动的持续时间dut()，则有下式成立：e(i)=ve(j)，l(
21、i)=vl(k)-dut()。若e(i)=l(i)，则活动 a i 就是关键路径上的关键活动。,V1 V2 V3 V4 V5 V6 V7 V8 V9 V10,(a1a2a3)(a4)(a5a6)(a7)(a8)(a9a10)(a11a13)(a12)(a14),ve：,0,4,3,2,7,8,13,10,15,21,l：,(0 0 2),(4),(4 3),(4),(7),(8 9),(15 13),(11),(16),vl：,0,4,3,4,7,8,13,11,16,21,关键活动：a1、a2、a4、a6、a8、a9、a13；,关键路径：V1V2V5V7V10 和 V1V3V6V7V10。,
22、21,7.6 最短路径,我们经常需要求解从某点（源点-source)出发到达另一点（终点-destination)的最短路径。当然，我们可以先求出这两点间的所有简单路径，再从中选出最短路径，但这种方法未免太低效率了，有没有更好的办法呢？,单源最短路径：从某源点到其它所有顶点间的最短路径。,顶点对间最短路径：各顶点到其它所有顶点间的最短路径。,求下图中 v1到各顶点的最短路径：,V1 到各点的最短距离为：4、3、5 和 2；,我们可以通过调用 n 次 Dijkstra 算法求的每对顶点间的最短路径，时间复杂度为 O(n3)。但还能有其它的求解办法吗？,Floyd定义了n 阶方阵序列 A(0)、A(1)、A(k)、A(n)，其中 A(0)为邻接矩阵，其它方阵 A(i)则分别表示以 i 点为中间顶点时的各顶点间距离和路径。,求左图中各顶点间的最短路径，可先给出其邻接矩阵如右所示：,各点间最短距离为A(5)所示；,各点间最短路径除标出的外，其余的均是直达路径。,该方法的时间复杂度也为 O(n3)。但算法更清晰。,
