[高等教育]济南大学数据结构 第七章.doc

《[高等教育]济南大学数据结构 第七章.doc》由会员分享，可在线阅读，更多相关《[高等教育]济南大学数据结构 第七章.doc（32页珍藏版）》请在三一办公上搜索。

1、第七章 图ABCDE图是一种较线性表和树更为复杂的数据结构。线性表: 线性结构（前驱、后继）树: 层次结构（父子）图: 任意两个数据元素之间都可能相关（邻接） 7.1 图的定义和基本术语图 G 是由两个集合顶点集 V(G) 和边集 E(G) 组成的，记作G=( V(G)，E(G) )，简称G=(V，E)。V是顶点的有穷非空集合 E是两个顶点之间的关系，即边的有穷集合 ABCDE无向图和有向图 无向图: 边是顶点的无序对，即边没有方向性。v1v2v3v5v4V = v1 , v2 , v3 , v4 , v5 E = ( v1 , v2 ) , ( v1 , v4 ) , ( v2 , v3 )

2、 , ( v2 , v5 ) , ( v3 , v4 ) , ( v3 , v5 ) ( v1 , v2 )表示顶点 v1 和 v2 之间的边( v1 , v2 ) = ( v2 , v1 )有向图: 其边是顶点的有序对，即边有方向性。v1v2v4v3V = v1 , v2 , v3 , v4 E = , , , 通常有向图的边称为弧，表示顶点 v1 到 v2 的弧。称 v1 为弧尾，称 v2 为弧头。 带权无向图(无向网) 和 带权有向图(有向网)有时对图的边或弧赋予相关的数值，这种与图的边或弧相关的数值叫做权。 ABCDE53821497这种带权的图通常称为网。 带权的无向图称为无向网。带

3、权的有向图称为有向网。性质: 若用 n 表示图中顶点数目，用 e 表示边或弧的数目，若在图中不存在顶点到自身的边或弧，则对于有向图，0 e n(n-1)对于无向图，0 e 1/2n(n-1)证明: 0 e 显然成立对有向图来说， 每个顶点至多可发出 n-1 条弧，共 n 个顶点，故至多有 n(n-1) 条弧，即 e n(n-1) ；对无向图来说，由于边无方向，则任一两个顶点 v1 和 v2，都有 ( v1 , v2 ) = ( v2 , v1 ) ，故至多有 n(n-1) 条边 ；完全图、有向完全图、稀疏图、稠密图 有 1/2n(n-1) 条边的无向图称为完全图。 有 n(n-1) 条弧的有向

4、图称为有向完全图。 v1v2v4v3v1v2v3有很少条边或弧的图称为稀疏图。 反之称为稠密图。 子图假设有两个图 G=(V, E) 和 G=(V, E) ，如果 V V，且 E E，则称 G 为 G 的子图。 v1v2v4v3求子图v1v1v3v1v4v3v1v2v4v3v1v2v4v3v1v2v3v5v4子图有v1v2v3v5v1v2v5v4v1v2v3v5v4邻接与关联vv对于无向图 G=(V, E)，如果存在边 (v, v)，则称顶点 v 和 v 互为邻接点，即 v 和 v 相邻接。 称边 (v, v) 与顶点 v 和 v 相关联。 vv对于有向图 G=(V, E) ，如果存在弧 ，则

5、称顶点 v 邻接到顶点 v，顶点 v 邻接自顶点 v 。 称弧 和顶点 v, v 相关联。顶点的度对于无向图，顶点 v 的度是和 v 相关联的边的数目，记做TD(v)。 v1v2v3v5v4顶点 v3 的度为对于有向图，顶点 v 的度 TD(V) 分为两部分出度、入度。 以顶点 v 为头的弧的数目称为 v 的入度，记为ID(v) ；以顶点 v 为尾的弧的数目称为 v 的出度，记为OD(v)； 顶点 v 的度为 TD(v) = ID(v) + OD(v)。 v1v2v4v3顶点 v1 的出度为 2顶点 v1 的入度为 1顶点 v1 的度为 3性质: 对于一个图(无向图、有向图)，如果顶点 vi

6、的度为TD(vi)，那么具有 n 个顶点、e 条边或弧的图，必满足如下关系e = TD(vi)12i = 1nv1v2v3v5v4v1v2v4v3无向图、有向图的边或弧均计算两遍。路径、回路(环)、链、简单路径、简单回路无向图 G 中若存在一条有穷非空序列 w = v0 e1 v1 e2 v2 ek vk ，其中 vi 和 ei 分别为顶点和边，则称 w 是从顶点 v0 到 vk 的一条路径。v0v1v2vk-1vk. . .e1e2ek顶点 v0 和 vk 分别称为路径 w 的起点和终点。路径的长度是路径上的边的数目。w 的长度为 k起点和终点相同的路径称为回路(环)。v0v1v2vk-1v

7、k. . .e1e2ek若路径 w 的边 e1 , e2 , , ek 互不相同，则称 w 为链。若路径 w 的顶点 v0 , v1 , 。, vk 互不相同，则称 w 为简单路径。链是否为简单路径? 不一定简单路径是否为链? 一定起点和终点相同的简单路径称为简单回路(简单环)。e1e2e3e4e5有向图 G 中若存在一条有穷非空序列 w = v0 e1 v1 e2 v2 ek vk ，其中 vi 和 ei 分别为顶点和弧，则称 w 是从顶点 v0 到 vk 的一条路径。v0v1v2vk-1vk. . .e1e2ek链简单路径回路简单回路连通、连通图、连通分量、强连通图、强连通分量无向图G，如

8、果从顶点 v 到顶点 v 有路径，则称 v 和 v 是连通的。 如果对于无向图 G 中任意两个顶点 vi , vj V, vi 和 vj 都是连通的，则称 G 是连通图。 v1v2v3v5v4是否为连通图连通分量指的是无向图中的极大连通子图。 ABCLHDEFGH非连通图连通分量为ABCLHDEFGHv1v2v3v5v4有向图G，如果从顶点 v 到顶点 v 有路径 或 从顶点 v 到顶点 v 有路径，则称 v 和 v 是连通的。 在有向图 G 中，如果对于每一对 vi, vj V，vivj ，从 vi 到 vj 和 从 vj 到 vi 都存在路径，则称 G 是强连通图。 v1v2v4v3是否为

9、强连通图有向图中的极大强连通子图称作有向图的强连通分量。 v1v2v4v3非强连通图强连通分量v2v1v4v3注意生成树、生成森林 对无向图而言一个连通图 G 的一个包含所有顶点的极小连通子图 T 是 (1) T 包含 G 的所有顶点 n 个(2) T 为连通子图(3) T 包含的边数最少T 是一棵有 n 个顶点，n-1 条边的生成树。ABCLHJ性质: 一个有n个顶点的连通图的生成树有且仅有n-1条边。1. 如果一棵生成树有 n 个顶点和小于 n-1 条边，则为非连通图。构成一棵 n 顶点生成树需要 n-1 条边，少于 n-1 ，则必有边断开，不再连通。2. 如果一棵生成树有 n 个顶点和多

10、于 n-1 条边，则一定有环。构成一棵 n 顶点生成树需要 n-1 条边，若再添加一条边，必会使得与它关联的那两个顶点之间有了第二条路经。ABCLHJ性质: 一个连通图的生成树并不唯一ABCLHJABCLHJABCLHJ生成树ABCLHJ删除环中的任一条边非连通图的各连通分量的生成树构成了非连通图的生成森林。ABCLHDEFGS生成森林ABCLHDEFGS7.2 图的存储结构顺序存储邻接矩阵链式存储邻接表邻接多重表十字链表7.2.1 邻接矩阵设图 G = ( V ，E ) 具有 n(n1) 个顶点 v1 , v2 , 。 , vn 和 m 条边或弧 e1 , e2 , , em ，则 G 的邻

11、接矩阵是 nn 阶矩阵，记为 A(G) 。邻接矩阵存放 n 个顶点信息和 n2 条边或弧信息。其每一个元素 aij 定义为:aij = 0 顶点 vi 与 vj 不相邻接1 顶点 vi 与 vj 相邻接例，有向图 Gv1v2v4v3A(G) = 1 2 3 412340 1 1 00 0 0 00 0 0 11 0 0 0 例，无向图 Gv1v2v3v5v40 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0A(G) = 1 2 3 4 512345邻接矩阵数据类型定义int AdjMatrixVertex_NUMVertex_NUM;优点:1. 容易判断

12、任意两个顶点之间是否有边或弧。2. 容易求取各个顶点的度。例无向图 Gv1v2v3v5v40 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 01 2 3 4 5A(G) = 12345无向图，顶点 vi 的度是邻接矩阵中第 i 行或第 i 列的元素之和。例 G1中，v1 的度为 2 ，v2 的度为 3 。v1v2v4v31 2 3 40 1 1 00 0 0 00 0 0 11 0 0 0A(G) = 1234有向图，顶点 vi 的出度是邻接矩阵中第 i 行的元素之和。顶点 vi 的入度是邻接矩阵中第 i 列的元素之和。例 v1 的度为 2+1=3。1 2

13、 3 412340 1 1 00 0 0 00 0 0 11 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 01 2 3 4 512345无向图有向图v1v2v3v5v4v1v2v4v3无向图的邻接矩阵都是对称矩阵。有向图的邻接矩阵一般不对称。带权图(网) 的邻接矩阵v65v1v2v3v5v4487935651 1 2 3 4 5 6 5 7 4 8 9 5 6 5 A = 123456 3 1 aij = wij 顶点 vi 与 vj 相邻接 顶点 vi 与 vj 不相邻接7.2.2 邻接表对图中每一个顶点建立一个单链表，指示与该顶点邻接的

14、顶点和关联的边或出弧。v1v2v3v5v4e1e2e3e4e5e601234v1v2v3v4v53e21e14e42e30e14e63e51e32e50e22e61e4adjvexnextarcarcinfo边结点vexinfofirstarc顶点结点vexinfo : 顶点的信息 adjvex : 邻接顶点位置firstarc : 第一条关联边结点 arcinfo : 边的信息 nextarc : 下一条关联边结点邻接表数据类型定义typedef struct ArcNode int adjvex ; ArcInfo data ; struct ArcNode * nextarc ; Arc

15、Node ;typedef struct VNode VertexInfo data ; ArcNode * firstarc ; Vnode , AdjListVertex_Num ;无向图 Gv1v2v3v5v4无向图 Ge1e2e3e4e5e601234v1v2v3v4v53e21e14e42e30e14e63e51e32e50e22e61e4如何获取顶点的度？顶点 vi 的度为第 i 条链中的结点数。需要多少存储空间？(设n个顶点，e条边)n + 2e有向图 Ge1e2v1v2v4v3e3e42e21e13e30e40123v1v2v3v4如何获取顶点的度？顶点 vi 的出度为邻接表第

16、 i 条链中的结点数。顶点 vi 的入度为逆邻接表第 i 条链中的结点数。需要多少存储空间？2n + 2e为了方便求顶点的入度，引入逆邻接表0e13e40e22e30123v1v2v3v40 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 001 1 0 01 2 3 4 51234501234v1v2v3v4v53e21e14e42e30e14e63e51e32e50e22e61e4邻接矩阵与邻接表存储空间求顶点的度判断两个顶点是否关联7.3 图的遍历与树的遍历类似，如果从图中某一顶点出发访遍图中所有顶点，且使每一个顶点仅被访问一次，这一过程称为图的遍历。图的遍历算法是求解

17、图的连通性问题、生成树、和拓扑排序等算法的基础。通常有两条遍历图的路径: 深度优先搜索、广度优先搜索。7.3.1 深度优先搜索v1v2v3v5v4v6v7v8图可分为三部分:基结点第一个邻接结点所能导出的子图其它邻接顶点所能导出的子图深度优先搜索是类似于树的先序遍历的一种方法。过程分析v1v2v3v5v4v6v7v8v1v2v3v4v6v8v5v7深度优先搜索顺序: v1 v2 v4 v8 v5 v3 v6 v7 栈实现深度优先搜索v1v2v3v4v6v8v5v7v1v2v4v8v5v3v6v7总是从栈顶出发搜索！栈顶元素必须等到所有邻接顶点均被访问过后方能出栈！深度优先搜索顺序: v1 v2

18、 v4 v8 v5 v3 v6 v7void DFSTraverse ( Graph G ，int v ) initstack(S) ；所有顶点visited函数置为false ;Push(S , v) ； visitedv = TRUE ；printf(v) ；while ( ! StackEmpty(S) ) L: Gettop(S , v) ； /获取栈顶元素for ( w=FirstAdjVex(G,v) ；w=0 ；w=NextAdjVex(G, v, w) )if ( !visitedw ) Push(S , w) ； visitedw = TRUE ；printf(w) ；Got

19、o L ； /访问栈顶元素的全部邻接顶点Pop(S) ；7.3.2 广度优先搜索把图人为的分层，按层遍历。v1v2v3v5v4v6v7v8只有父辈结点被访问后才会访问子孙结点！广度优先搜索类似于树的层次遍历，过程分析v1v2v3v5v4v6v7v8v1v2v3v4v5v6v7v8广度优先搜索顺序: v1 ， v2 ， v3 ， v4 ， v5 ， v6 ， v7 ， v8队列实现广度优先搜索算法void BFSTraverse ( Graph G ，int v ) / visited0.n-1 初始均为 0 ；v 指示顶点在数组中的位置 ；InitQueue(Q) ； EnQueue(Q ,

20、v) ； visitedv=TRUE ；printf(v) ；while ( ! QueueEmpty(Q) ) DeQueue(Q , u) ；for ( w=FirstAdjVex (G,u) ；w=0 ；w=NextAdjVex(G, u, w) )if ( ! visitedw ) EnQueue(Q , w) ； visitedw = TRUE ；printf(w) ； /其邻接顶点全部送入队列书面作业:分别应用 DFS, BFS 实现遍历 要求尽量按顶点序号顺序搜索21543108612147151311916171819207.4 图的连通性问题7.4.1 无向图的连通分量利用

21、DFS 或 BFS 获取连通分量ABCLHDEFGSDFSABHLCDEFGS7.4.2 无向图的生成树利用 DFS 或 BFS 获取生成树例，DFSv1v2v3v5v4v6v7v8v1v2v3v4v6v8v5v7DFS生成树例，BFSv1v2v3v5v4v6v7v8BFS生成树v1v2v3v4v5v6v7v87.4.3 最小生成树一个无向图可以对应多个生成树。一个带权无向图(无向网)同样可以对应多个生成树。v1v2v3v5v4v61556536642v1v2v3v5v4v615342生成树一棵生成树的代价定义为树上各边的权之总和。代价最小的生成树称为最小生成树。实际价值？如何求取最小生成树？

22、v1v2v3v5v4v653642引论: 假设 N = ( V , E ) 是一个连通网，U 是顶点集 V 的非空子集，若 ( u , v ) 是一条具有最小权值的边，其中 uU，vV-U，则必存在一棵包含边 ( u , v ) 的最小生成树。假设连通网 N 的任何一棵最小生成树都不包含边 ( u , v ) ；设 T 是 N 的一棵最小生成树，当把边 ( u , v ) 加入到 T 中时，T 中必存在一条包含 ( u , v ) 的回路 ；uvuvu1v1. . . . . . . . .UV-U删去边 ( u , v ) ，可得到另一棵生成树 T ；由于边 ( u , v ) 的代价最小，

23、则 T 的代价不高于 T 的代价，即 T 是一棵包含边 ( u , v ) 的最小生成树。矛盾。Prim 算法思想：N = ( V , E ) 是具有 n 个顶点的连通网，设 U 是最小生成树中顶点的集合，设 TE 是最小生成树中边的集合； 初始，U = u1 ，TE = ，重复执行:在所有 uU，vV-U 的边 ( u , v ) 中寻找代价最小的边( u , v ) ，并纳入集合 TE 中；同时将 v 纳入集合 U 中；直至 U = V 为止。集合 TE 中必有 n-1 条边。 例，v1v2v3v5v4v61556536642v1v31v25v53v64v42初始: U = v1 ，V-U

24、 = v2 , v3 , v4 , v5 , v6 TE = U = v1 , v3 ，V-U = v2 , v4 , v5 , v6 U = v1 , v3 , v6 ，V-U = v2 , v4 , v5 U = v1 , v3 , v4 , v6 ，V-U = v2 , v5 U = v1 , v2 , v3 , v4 , v6 ，V-U = v5 U = v1 , v2 , v3 , v4 , v5 , v6 ，V-U = 重点: 边一定存在于 U 与 V-U 之间。Kruskal 算法思想：N = ( V , E ) 是 n 顶点的连通网，设 E 是连通网中边的集合； 构造最小生成树

25、 N = ( V , TE )，TE 是最小生成树中边的集合，初始 TE = ；重复执行:选取 E 中未访问过的权值最小的边 ( u , v ) ，判断边 ( u , v ) 与 TE 中的边是否构成回路 ？否，将边 ( u , v ) 纳入 TE 中，并从 E 中删除边 ( u , v ) ；直至 E 为空 ；例，v1v2v3v5v4v61556536642v1v31v4v62v2v5345当前权值最小边 ( v5 , v6 )初始 TE = 作业. 构造最小生成树 要求：写中间过程1245631651062111143318197.5 最短路径兰州太原北京济南徐州郑州西安112092072

26、0210540340640190旅客希望停靠站越少越好，则应选择济南北京太原兰州旅客考虑的是路程越短越好，则应选择济南徐州郑州西安兰州带权图的最短路径计算问题通常在实际中，航运、铁路、船行都具有方向性，故我们以带权有向图为例介绍最短路径算法。 从单个源点到其余各顶点的最短路径算法。 任一对顶点之间的最短路径算法。7.5.1 从单个源点到其余各顶点的最短路径算法 Dijkstra 算法思想: 利用已得到的顶点的最短路径来计算其它顶点的最短路径。贪心思想: 利用局部最优来计算全局最优。例，例，v5v0v1v4v3601005v2103020 1050求从 v0 到其余各顶点的最短路径。Di 表示

27、v0 到 vi 的最短路径的长度Pathi表示v0 到 vi 的最短路径上的顶点1. 初始，Di 的值为 v0 到 vi 的弧的权值显然，Di 中的最小值 D2 便是 v0到 v2 的最短路径的长度，Path2=( v0 , v2 )v0 v1 v2 v3 v4 v5Di 10 30 100例例，v5v0v1v4v3601005v2103020 10502. 如何寻找下一条最短路径？设下一条最短路径的终点是 vj ，则这条最短路径或者是 ( v0 , vj ) 、或者是 v0 经过 v2 到达 vj 的路径 ；其中取 Di(D2除外) 中的最小值得到 v4，Path4=( v0 , v4 )

28、。v0 v1 v2 v3 v4 v5Di 10 60 30 1003. 如何寻找下一条最短路径？例，v5v0v1v4v3601005v21030201050带权邻接矩阵 10 30 1000 1 2 3 4 5 5 50 10 20 60 012345v21030100v0v2v2106030100v0v4v430v2 , v450 90v0v4v3v350v2 , v4 , v3 60v0v4v3v5v560v2 , v4 , v3 , v5 v1v1v2v3v4v5最短路径新终点S顶点路径长度每次修改都用的是最新加入集合 S 的顶点贪心思想并不是万能的！货郎担问题1020109020v0v

29、1v2v3贪心思想 v0 ， v1 ， v2 ， v3 110最优解 v0 ， v1 ， v2 ， v3 507.5.2 每一对顶点之间的最短路径算法 Floyd 算法算法1: 每次以一个顶点为源头，重复执行 Dijkstra 算法 n 遍，便可得到每一对顶点之间的最短路径。算法时间复杂度: O(n3)算法2: Floyd 算法算法时间复杂度: O(n3)Floyd 算法思想初始，从图的带权邻接矩阵 D(-1) 出发，作为顶点 vi 到 vj 的最短路径。0. 考虑经过 v0 是否会存在更短的路径，即 ( vi , v0 , vj ) 是否存在(判断弧( vi , v0 ) 和( v0 , v

30、j ) 是否存在)；vivjv0若存在，比较 ( vi , vj ) 与 ( vi , v0 )+ (v0 , vj ) ，小者作为从 vi 到 vj 且中间顶点只经过 v0 的最短路径，得新矩阵 D(0) 。D(-1) D(0)1. 考虑经过 v1 是否会存在更短的路径，即 ( vi v1 vj ) 是否存在(如果 ( vi v1 ) 和 ( v1 vj ) 分别是当前找到的中间顶点只经过 v0 的最短路径) ；vivjv0v1若存在，比较 ( vi vj ) 与 ( vi v1 )+ (v1 vj ) (D(0) ，小者作为从 vi 到 vj 的中间顶点经过 v0 、v1的最短路径，得新矩

31、阵 D(1) 。k. 考虑经过 vk 是否会存在更短的路径，即 ( vi vk vj ) 是否存在(如果 ( vi vk ) 和 ( vk vj ) 分别是当前找到的中间顶点经过 v0 、v1 vk-1的最短路径) ；vivjvk-1vk若存在，比较 ( vi vj ) 与 ( vi vk )+ (vk vj ) (D(k-1) ，小者作为从 vi 到 vj 的中间顶点经过 v0 、v1 vk的最短路径，得新矩阵 D(k) 。算法描述定义一个 n 阶方阵序列： D(-1) , D(0) , D(1) , , D(k) , , D(n-1)D(k)ij 表示从vi到vj的中间顶点经过 v0 、v

32、1 vk的最短路径的长度。初始， D(-1)ij = arcsij ；循环 n 遍，依次考虑将 v0 , v1 , , vn-1 加入到路径中D(k)ij = Min D(k-1)ij , D(k-1)ik + D(k-1)kj 算法时间复杂度: O(n3)例，v1v2v0642113邻接矩阵0 1 20 4 116 0 23 0012D(2)ij = Min D(1)ij , D(1)i2 + D(1)2j D(-1)0 4 11 6 0 23 00 1 2012D(0)0 1 20120411602370046027063060237045计算时不用考虑对角线计算时不用考虑第 k 行和第

33、k 列作业. 求 A 到其它各点的最短路径及长度 要求：中间过程ABECDF451030353201515501020作业. 求所有顶点对之间的最短路径及长度 要求：中间过程7.6 有向无环图及应用一个无环的有向图称为有向无环图，简称 DAG 图。有向树DAG 图有向图给定一个图，如何判断是否存在环？方法1 利用深度优先搜索算法，若将要指向的顶点已被访问过，则存在环。abcd无向图abcd有向图abcdbabcdb可正确判定可正确判定方法2 拓扑排序法课程编号课程名称先决条件C1C2C3C4C5程序语言基础离散数学数据结构微机原理编译原理C6操作系统C1C1 , C2C3C3 , C4表示课程

34、之间先后关系的有向图C1C2C3C5C4C6这种用顶点表示活动，用弧表示活动之间的先后关系的有向无环图称为顶点表示活动的网 AOV 网。对 AOV 网中的所有顶点进行一个排序，如果满足: 若 i 是 j 的前驱顶点，则结点 i 必排在结点 j 之前则称这样的排序为拓扑排序。例，表示课程之间先后关系的 AOV 网C1C2C3C5C4C6例，拓扑排序可以为:C1 C2 C3 C5 C4 C6C4 C1 C2 C3 C5 C6表示课程之间先后关系的 AOV 网性质: 若AOV 网中的所有顶点都在它的拓扑排序中，则该 AOV 网中必定不存在环；否则必存在环。思想:1. 在有向图中选取一个没有前驱的顶点并打印 ；