大学教程(零起点)数据结构-1图

1、问题：问题：电子地图中从起点到终点的最短路径求取电子地图中从起点到终点的最短路径求取任务分解任务分解子任务子任务1，电子地图在计算机中的存储方式，电子地图在计算机中的存储方式子任务子任务2，计算机起点到终点的最短路径的方法，计算机起点到终点的最短路径的方法问题：问题：电子地图中从起点到终点的最短路径求取电子地图中从起点到终点的最短路径求取子任务子任务1分解：电子地图在计算机中的存储方式分解：电子地图在计算机中的存储方式进一步分解子任务：进一步分解子任务： 1.1 抽象出电子地图的表示形式抽象出电子地图的表示形式 1.2 根据表示形式抽象出电子地图的逻辑形式根据表示形式抽象出电子地图的逻辑形式

2、1.3 根据逻辑形式设计存储结构根据逻辑形式设计存储结构 1.4 根据设计的存储结构定义数据结构根据设计的存储结构定义数据结构问题：问题：电子地图中从起点到终点的最短路径求取电子地图中从起点到终点的最短路径求取子任务子任务1分解：电子地图在计算机中的存储方式分解：电子地图在计算机中的存储方式进一步分解子任务：进一步分解子任务： 1.1 抽象出电子地图的表示形式抽象出电子地图的表示形式潍坊潍坊平度平度莱州莱州招远招远蓬莱蓬莱烟台烟台威海威海文登文登乳山乳山潍坊潍坊莱阳莱阳栖霞栖霞莱西莱西即墨即墨青岛青岛胶州胶州胶南胶南黄岛黄岛抽象出电子地图的表示形式抽象出电子地图的表示形式蓬莱蓬莱潍坊潍坊平度平

3、度莱州莱州招远招远烟台烟台威海威海文登文登乳山乳山潍坊潍坊莱阳莱阳栖霞栖霞莱西莱西即墨即墨青岛青岛胶州胶州胶南胶南黄岛黄岛200100150190220120150805020110906060507013070701108555抽象出电子地图的表示形式抽象出电子地图的表示形式蓬莱蓬莱潍坊潍坊平度平度莱州莱州招远招远烟台烟台威海威海文登文登乳山乳山潍坊潍坊莱阳莱阳栖霞栖霞莱西莱西即墨即墨青岛青岛胶州胶州胶南胶南黄岛黄岛200100150190220120150805020110906060507013070701108555抽象出电子地图的表示形式抽象出电子地图的表示形式OABCLPRQNKJ

4、MIHGDEF200100150190220120150805020110906060507013070701108555抽象出电子地图的表示形式抽象出电子地图的表示形式问题：问题：电子地图中从起点到终点的最短路径求取电子地图中从起点到终点的最短路径求取子任务子任务1分解：电子地图在计算机中的存储方式分解：电子地图在计算机中的存储方式进一步分解子任务：进一步分解子任务： 1.1 抽象出电子地图的表示形式抽象出电子地图的表示形式 用点和线表示地图，线上的数值表示距离用点和线表示地图，线上的数值表示距离 1.2 根据表示形式抽象出电子地图的逻辑形式根据表示形式抽象出电子地图的逻辑形式图的定义：图的

5、定义：权的定义：权的定义：扩展：有向图定义、其他图的术语的定义扩展：有向图定义、其他图的术语的定义v1v2v5v4v3如果每条边都没有方向，则为无向图如果每条边都没有方向，则为无向图 (vi,vj)(vi,vj)和和(vj,vi)(vj,vi)表示同一条边表示同一条边如果每条边都有方向，则称有向图如果每条边都有方向，则称有向图有向图中用箭头表示弧的方向，箭头从弧尾指向弧头有向图中用箭头表示弧的方向，箭头从弧尾指向弧头例如右图中的弧：例如右图中的弧：，v2v2是弧尾，是弧尾，v4v4是弧头是弧头v1v2v5v4v3v2v1v4v3G2=V,EG2=V,EV= v1,v2,v3,v4,v5 V=

6、v1,v2,v3,v4,v5 ，E=, ,E=, ,邻接点、相关边邻接点、相关边无向图中存在边无向图中存在边(vi,vj)(vi,vj)，则称，则称vivi和和vjvj互为邻接点互为邻接点 同时称边同时称边(vi,vj)(vi,vj)依附于顶点依附于顶点vi,vjvi,vj (vi,vj) (vi,vj)是与是与vivi和和vjvj相关联的边相关联的边在有向图中，若存在弧在有向图中，若存在弧，也称相邻接，也称相邻接， 但要区分弧的头和尾但要区分弧的头和尾G1=(V1，E1); V1= v1,v2,v3,v4,v5 E1= (v1,v2),(v2,v3),(v3,v5),(v2,v4),(v2,

7、v5) G2=(V2，E2)V2=v2,v3,v5E2=(v2,v3),(v2,v5),(v3,v5) 生成树生成树包含无向图包含无向图G G 所有顶点的的极小连通子图所有顶点的的极小连通子图若若T T是是G G 的生成树当且仅当的生成树当且仅当T T 满足如下条件满足如下条件 T T是是G G 的连通子图的连通子图 T T包含包含G G 的所有顶点的所有顶点 T T中无回路中无回路 若连通图若连通图G G的顶点个数为的顶点个数为n n，则，则G G的生成树边数为的生成树边数为n-1n-1 如果如果G G的一个子图的一个子图GG的边数大于的边数大于n-1n-1，则，则GG中一定有中一定有环环

8、相反，如果相反，如果GG的边数小于的边数小于n-1n-1，则，则GG一定不连通一定不连通结论结论 V0V0 V4V4 V3V3 V1V1 V2V2824653习题习题1.1.（1 1）设有无向图）设有无向图G=(V,E)G=(V,E)和和G=(V,E)G=(V,E)，若，若GG是是G G的生成树，则下面不正确的说法是（的生成树，则下面不正确的说法是（ ） GG为为G G的子图的子图 GG为为G G的连通分量的连通分量 C. GC. G为为G G的极小连通子图且的极小连通子图且V=V V=V D. GD. G是是G G的无环子图的无环子图答案：答案：B B蓬莱蓬莱潍坊潍坊平度平度莱州莱州招远招远

9、烟台烟台威海威海文登文登乳山乳山潍坊潍坊莱阳莱阳栖霞栖霞莱西莱西即墨即墨青岛青岛胶州胶州胶南胶南黄岛黄岛200100150190220120150805020110906060507013070701108555抽象出电子地图的表示形式抽象出电子地图的表示形式OABCLPRQNKJMIHGDEF200100150190220120150805020110906060507013070701108555抽象出电子地图的表示形式抽象出电子地图的表示形式选择选择/设计合适的存储结构设计合适的存储结构问题：问题：电子地图中从起点到终点的最短路径求取电子地图中从起点到终点的最短路径求取任务分解任务分解子

10、任务子任务1，电子地图在计算机中的存储方式，电子地图在计算机中的存储方式子任务子任务2，计算机起点到终点的最短路径的方法，计算机起点到终点的最短路径的方法 2.1 图的相关操作如何实现图的相关操作如何实现 2.1.1 图的遍历操作图的遍历操作 2.2.2 图的连通性及最小生成树图的连通性及最小生成树 2.2.3 拓扑排序及拓扑序列拓扑排序及拓扑序列 2.2 图中最短路径的计算方法图中最短路径的计算方法邻接矩阵表示法邻接矩阵表示法邻接表表示法邻接表表示法若若G G是网是网若若G G是图是图 Aij=0 0 无边无边1 1 有边有边Aij=0 0或或 无边无边权值权值 有边有边V1V2V3V4V1

11、V2V3V435961 1，无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的2 2，存储无向图的邻接矩阵需要，存储无向图的邻接矩阵需要n(n+1)/2n(n+1)/2个单元，个单元， 与边数无关，只与顶点数有关。与边数无关，只与顶点数有关。3 3，无向图，无向图vivi的度是第的度是第i i行行( (列列) )中中1 1的个数，的个数， 边数是矩阵中边数是矩阵中1 1个数的一半个数的一半4 4，有向图第，有向图第i i行行1 1的个数是的个数是vivi的出度的出度 第第i i列列1 1的个数是的个数是vivi的入度的入度 1. 1. 无向图的邻接表无向图的邻接表顶点数组顶点数组与顶点邻接的顶

12、点链表与顶点邻接的顶点链表表头结点表头结点表结点表结点2.2.有向图的邻接表（有向图的邻接表（出出边表）和逆邻接表（边表）和逆邻接表（入入边表）边表）逆邻接表逆邻接表邻接表邻接表逆邻接表逆邻接表邻接表邻接表邻接表邻接表习题习题2.2.（2 2）已知无向图）已知无向图G G的结点数为的结点数为n n，边数为，边数为e e，其邻，其邻接表表示中的表结点数与表头结点数之和为接表表示中的表结点数与表头结点数之和为 答案：答案：n+2en+2e表表结结点点数数表表头头结结点点数数1.1.邻接表表示法是借助邻接表表示法是借助_来反映顶点间的来反映顶点间的邻接关系，其中的结点称为表结点。邻接关系，其中的结点

13、称为表结点。 习题习题答案：单链表答案：单链表3. 3. 对于无向图的邻接矩阵，顶点对于无向图的邻接矩阵，顶点vivi的度是的度是_。对于有向图的邻接矩阵，顶点对于有向图的邻接矩阵，顶点vivi的出度的出度ODOD（vivi）为）为_，顶点，顶点vivi的入度的入度ID(vi)ID(vi)是是_。习题习题答案：答案：矩阵第矩阵第i i行（列）非零元素的个数；行（列）非零元素的个数；矩阵第矩阵第i i行非零元素的个数；行非零元素的个数；矩阵第矩阵第i i列非零元素的个数；列非零元素的个数； 有两种遍历方法有两种遍历方法： 深度优先遍历（深度优先遍历（DFSDFS：Depth First Sear

14、chDepth First Search） 广度优先遍历（广度优先遍历（BFSBFS：Breadth First SearchBreadth First Search）一一 、深度优先遍历（、深度优先遍历（DFSDFS）从图中某顶点从图中某顶点v v出发：出发： 1 1）访问顶点）访问顶点v v；2 2）依次从）依次从v v的的未被访问的邻接点未被访问的邻接点出发，继续对图进行出发，继续对图进行深度优先遍历；深度优先遍历；由于没有规定访问邻接点的顺序，由于没有规定访问邻接点的顺序，DFSDFS序列不唯一序列不唯一abchdekfgachkfedbgvoid dfs(int v)void dfs

15、(int v) 访问访问v ;v ; visitv=1; visitv=1; 找到找到g g中中v v的第一个邻接点的第一个邻接点w;w; while( w while( w存在存在 ) ) if( visit w =0 ) if( visit w =0 ) dfs( w ); dfs( w ); 令令 w = gw = g图中图中v v的下一个邻接点的下一个邻接点 深度优先遍历算法深度优先遍历算法图中某未访问过的顶点图中某未访问过的顶点vivi出发：出发：1 1）访问顶点）访问顶点vi vi ；2 2）访问）访问 vi vi 的所有的所有未被访问未被访问的邻接点的邻接点w w1 1 ,w ,

16、w2 2 , w, wk k ；3 3）依次从这些邻接点出发依次从这些邻接点出发，访问它们的所有未被访问，访问它们的所有未被访问的邻接点的邻接点; ; 依此类推，直到图中所有访问过的顶点的邻依此类推，直到图中所有访问过的顶点的邻接点都被访问；接点都被访问；二、广度优先遍历（二、广度优先遍历（BFSBFS）Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w41 1一有向图一有向图G G的邻接表存储结构如图所示。现按深的邻接表存储结构如图所示。现按深度优先遍历算法，从顶点度优先遍历算法，从顶点V1V1出发，所得到的顶点序出发，所得到的顶点序列可能是列可能是 （ ）V1,V3, V2

17、 ,V4, V5 V1,V3, V2 ,V4, V5 V1, V3, V4, V2, V5 V1, V3, V4, V2, V5 V1,V2, V3, V4, V5 V1,V2, V3, V4, V5 V1, V3, V4, V5 ,V2 V1, V3, V4, V5 ,V2 习题习题答案：答案： 图的连通分量图的连通分量abcdegfaedcbgfabcdegfaedcbgf连通分量连通分量深度优先生成树深度优先生成树广度优先生成树广度优先生成树a ae ed dc cb bg gf fabcdegfaedcbgf连通分量连通分量深度优先生成树深度优先生成树广度优先生成树广度优先生成树abc

18、degfabcdegfaedcbgf图的连通分量图的连通分量对图进行对图进行dfs和和bfs，每次调用得到一个连通分量，每次调用得到一个连通分量思考题目：如何运用思考题目：如何运用dfs和和bfs判断图是否为连通图？判断图是否为连通图？abcdegfaedcbgf1. 1. 对有向图对有向图G,G,如果从任意顶点出发进行一次深度优如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是先或广度优先搜索能访问到每个顶点，则该图一定是完全图。完全图。判断题判断题生成树生成树包含无向图包含无向图G G所有顶点的极小连通子图称为所有顶点的极小连通子图称为G G的生成树的生成树若若

19、T T是是G G 的生成树当且仅当的生成树当且仅当T T 满足如下条件满足如下条件 T T是是G G 的连通子图的连通子图 T T包含包含G G 的所有顶点的所有顶点 T T中无回路中无回路abcdegfaedcbgfabcdegfaedcbgf 若连通图若连通图G G顶点个数为顶点个数为n n，则，则G G的生成树的边数为的生成树的边数为n-1n-1。 如果如果G G的一个子图的一个子图GG的边数大于的边数大于n-1n-1，则，则GG中一定中一定有环。有环。 相反，如果相反，如果GG的边数小于的边数小于n-1n-1，则，则GG一定不连通。一定不连通。结论结论abcdegfaedcbgfabc

20、degfaedcbgf 假设要在假设要在 n 个城市之间建立通讯联络网，个城市之间建立通讯联络网，则连通则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，如何条线路，如何在最节省经费的前提下建立这个通讯网？在最节省经费的前提下建立这个通讯网？最短路径计算问题中的延伸问题最短路径计算问题中的延伸问题1：利用最小生成树利用最小生成树 假设要在假设要在 n 个城市之间建立通讯联络网，个城市之间建立通讯联络网，则连通则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，如何条线路，如何在最节省经费的前提下建立这个通讯网？在最节省经费的前提下建立这个通讯网？abcdegf19514182

21、7168213ae12dcbgf7148531621假设用顶点表示城市，假设用顶点表示城市，边表示城市间的通信边表示城市间的通信线路，边上的权表示线路，边上的权表示费用费用abcdegf195141827168213ae12dcbgf7148531621abcdegf51827821ae12dcbgf8521abcdegf195141827168213ae12dcbgf7148531621abcdegf514168213aedcbgf148531621最小生成树最小生成树 若有一个连通的无向图若有一个连通的无向图G G，有，有n n个顶点，并且它的边是个顶点，并且它的边是有权值的。在有权值的。

22、在G G上构造生成树上构造生成树 G G , ,最小生成树最小生成树n-1n-1条边条边的权值之和最小的的权值之和最小的 G G 。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）算法一：（普里姆算法）算法一：（普里姆算法） 取图中任意一个顶点取图中任意一个顶点 v 作为生成树的根，之后往生作为生成树的根，之后往生成树上添加新的顶点成树上添加新的顶点 w。在添加的顶点在添加的顶点 w 和已经在生和已经在生成树上的顶点成树上的顶点v 之间必定存在一条边，并且该边的权值之间必定存在一条边，并且该边的权值在所有连通顶点在所有连通顶点 v 和和 w 之间的边中取值最小。之间的边中取值最小。之后继之

23、后继续往生成树上添加顶点，直至生成树上含有续往生成树上添加顶点，直至生成树上含有 n-1 个顶个顶点为止。点为止。abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和= 14+8+3+5+16+21 = 67v2v1v3v7v6v5v4645473具体做法具体做法: 先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然后从，然后从权值最小的边开始，若它的添加不使权值最小的边开始，若它的添加不使SG 中产生回路，中产生回路，则在则在 SG 上加上这条边，如此重复，直至加上上加上这条边，如此重复，直至加上

24、n-1 条边条边为止。为止。考虑问题的出发点考虑问题的出发点: 为使生成树上边的权值之和达到为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12dcbgf71485316217121819直到所有点都加入第一组或无可加入点为止直到所有点都加入第一组或无可加入点为止反复从第二组中选距离最小的反复从第二组中选距离最小的vkvk加到第一组中，每加到第一组中，每加入一个顶点加入一个顶点vkvk，修改源点，修改源点v v到各个顶点的距

25、离，到各个顶点的距离， 修改后再次选择距离最小点加入第一组修改后再次选择距离最小点加入第一组6020105051104010V1V2V3V4V5V01011060205054010V1V2V3V4V5V01011060205054010S0 S1 S2 S3 S4 S5 d0 d1 d2 d3 d4 d5 源点源点V0V0到到ViVi的距离：的距离：d d数组数组s s数组表示哪个点最短路径已求得数组表示哪个点最短路径已求得P0 P1 P2 P3 P4 P5 p p数组表示最短路径上数组表示最短路径上ViVi的前驱点的前驱点060找最小距离找最小距离修改修改s s数组数组修改距离数组修改距离数

26、组修改修改p p数组数组01040110100000012-1-10-10011417013S0 S1 S2 S3 S4 S5 d0 d1 d2 d3 d4 d5 源点源点V0V0到到ViVi的距离：的距离：d d数组数组s s数组表示哪个点最短路径已求得数组表示哪个点最短路径已求得P0 P1 P2 P3 P4 P5 p p数组表示最短路径上数组表示最短路径上ViVi的前驱点的前驱点060找最小距离找最小距离修改修改s s数组数组修改距离数组修改距离数组修改修改p p数组数组01040110100000012-1-10-10011417013V1V2V3V4V5V01011060205054010d0 d1 d2 d3 d4 d5 源点源点V0V0到到ViVi的距离：的距离：d d数组数组P0 P1 P2 P3 P4 P5 p p数组表示最短路径上数组表示最短路径上ViVi的前驱点的前驱点60输出源点到每个顶点的路径输出源点到每个顶点的路径 V2V2V0V0 V3 V3V2V2V0V0 V4V4V0V0 V5V5V3V3V2V2V0V0010402-1-100703V1V2V3V4V5V01011060205054010BDAC可求得拓扑有序序列：可求得拓