《数据结构与算法 Java版 教学课件 ppt 作者罗文劼 第5章 图结构》由会员分享，可在线阅读，更多相关《数据结构与算法 Java版 教学课件 ppt 作者罗文劼 第5章 图结构（56页珍藏版）》请在金锄头文库上搜索。
1、第5章 图结构,2019年5月25日,教学内容： 图的基本概念、图的存储方法、图的遍历、生成树和最小生成树、有向无环图及其应用、最短路径 教学目的： 理解图的基本概念及术语；掌握图的存储方法；熟练掌握图的两种遍历的算法思想、步骤；理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。 教学重点： 图的定义及其含义；图的邻接矩阵和邻接表存储方法；图的按深度优先搜索遍历和按广度优先搜索遍历方法；生成树和最小生成树的概念；Prim算法思想构造最小生成树按Prim算法思想；有向无环图的应用。 教学难点： 正确理解与区别图的常用术语；区别图的两种存储结构
2、的不同点及其应用场合；关键路径的算法思想；最短路径的算法思想。,2019年5月25日,5.1 引言,5.1.1 问题的提出 问题1：寻求走迷宫问题的解，迷宫可表示成图，求解即为寻求满足某种要求的从迷宫的入口结点到迷宫的出口结点的路径。 问题2：从公园入口处寻找一条参观某个动物的最短路径。 问题3：在几个村落之间铺设通讯线路，如何铺设最省钱。 问题4：计算机科学与技术专业的大学生，本科四年需要学习公共基础课、专业基础课、专业课几十门，每门课程都可能有先修课程的要求，如何合理安排课程的教学顺序，使学生能够顺利完成学业。 。,2019年5月25日,5.1.2 图的定义和术语,1图的定义 图(Grap
3、h)由一个顶点集合Vn和一个边（或者弧）集合En组成，通常记为：G(Vn,En)，其中Vn中有n(n0)个顶点，En中有e（e=0）条边，且每一条边都依附于Vn中的两个顶点vi, vj（i, j=1,2, n），该边用顶点偶对来表示，记为( vi,vj)。,2019年5月25日,2.图的相关术语 无向图 有向图 例：右图是一个有向图G2。 表示为： G2=(V2,E2) V2=v1,v2,v3,v4 E2=,2019年5月25日,(3) 邻接点、邻接边 (4) 完全图 (5) 稠密图、稀疏图 (6) 顶点的度、入度、出度 (7) 边的权、网图 (8) 路径和路径长度 (9) 回路、简单路径、简
4、单回路 (10) 子图 (11) 连通的、连通图、连通分量 (12) 强连通图、强连通分量 (13) 连通图（或子图）的生成树 (14) 非连通图的生成森林,2019年5月25日,5.1.3 图的基本操作,(1) CreatGraph(G) (2) DestroyGraph(G) (3) GetVex(G, v) (4) PutVex(G, v, value) (5) InsertVex(G, v) (6) DeleteVex(G, v) (7) InsertArc(G, v, w) (8) DeleteArc(G, v, w) (9) Traverse(G, v) (10) LocateVe
5、x(G, u) (11) FirstAdjVex(G, v) (13) NextAdjVex(G, v, w),2019年5月25日,5.2.1 邻接矩阵,1、邻接矩阵的存储思想 (1) 图中顶点顺序存储； (2) 用一个n*n矩阵（设图有n个顶点）来存储任意两个顶点之间边的信息，也就是各顶点之间的邻接关系。,若G是带权图，则邻接矩阵可定义为：,5.2 图的存储方法,2019年5月25日,用邻接矩阵表示法表示的无向图和网图如下图所示。,2019年5月25日,2、邻接矩阵的表示,class MGraph implements Graph VertexType vexs; /顶点表 EdgeTyp
6、e edges; /邻接矩阵 int vexnum; /图中结点的个数 int edgenum; /图中边的个数 MGraph(int vnum, int enum) /构造函数 vex=new VertexTypevnum; edges=new EdgeTypevnumvnum; vexnum=vnum; edgenum=enum; (其他成员函数) ,2019年5月25日,5、建立一个有向图邻接矩阵存储的算法,2019年5月25日,5.2.2 邻接表,1、邻接表的存储思想 右图给出无向图及对应的邻接表表示。,2019年5月25日,2、邻接表的两种结点结构,2019年5月25日,3、邻接表的
7、定义,class EdgeNode int adjvex; /用于存放邻接点序号 EdgeNode next; /指向下一个邻接点（或边） /若要表示边上信息，则应增加相关数据域info class VertexNode VertexType vertex; /用于存放顶点信息 EdgeNode firstedge; /第一条边的指针 Class ALGraph complements Graph VertexNode AdjList; /顶点结点向量 int vexnum /图中结点的个数 int edgenum /图中边的个数 ALGraph(int vnum, int enum) /构造
8、函数 AdjList=new VertexNodevnum; vexnum=vnum; edgenum=enum; (其他成员函数) ,2019年5月25日,2019年5月25日,有向图的逆邻接表 下图所示为有向图G2的邻接表和逆邻接表。,2019年5月25日,由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面： 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。 在图结构中，如果有回路存在，那么一个顶点被访问
9、之后，有可能沿回路又回到该顶点。 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。,5.3 图的遍历,2019年5月25日,5.3.1 深度优先搜索,深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。 1、深度优先搜索的概念,2019年5月25日,以下图的无向图G5为例，进行图的深度优先搜索。 v1 v2 v4v8 v5 v3v6v7,2019年5月25日,2、图的深度优先遍历算法,2019年5月25日,5.3.2 广度优先搜索,广度优先搜索（Breadth_First Search） 遍
10、历类似于树的按层次遍历的过程。 1、广度优先搜索的概念,2019年5月25日,例如，对下图所示无向图G5 进行广度优先搜索遍历，得到的顶点访问序列为： v1v2 v3 v4 v5 v6 v7 v8,2019年5月25日,2、图的广度优先遍历算法,2019年5月25日,1 . 无向图的连通性 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。,5.3.3遍历图的简单应用,2019年5月25日,2019年5
11、月25日,2. 有向图的连通性,有向图的连通性不同于无向图的连通性，可分为弱连通、单侧连通和强连通。对有向图的强连通性以及强连通分量的判定，可通过对以十字链表为存储结构的有向图的深度优先搜索实现。,2019年5月25日,5.4 生成树和生成森林,5.4.1 生成树和生成森林 1.生成树和生成森林的概念,2019年5月25日,对于非连通图，通过这样的遍历，将得到的是生成森林。例如，下图所示为一个无向图及其深度优先生成森林，它由三棵深度优先生成树组成。,2019年5月25日,2. 生成森林的构建算法,2019年5月25日,5.4.2 最小生成树,下图 (a)、(b)和(c)所示的均为无向连通图G5
12、的生成树。,1、 最小生成树的概念,2019年5月25日,2、如何找到一个连通网络的最小生成树？,(1) MST性质： MST性质：设G(Vn, En)是一个连通网络，U是顶点集Vn的一个真子集。若(u，v)是G中所有的一个端点在U（即uU）而另一个端点不在U（即vVnU）里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。,2019年5月25日,5.4.3 构造最小生成树的Prim算法,1、Prim算法,Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。 Uu1,T=; while (UV)do (u,v)minwuv|uU,vVU TT(u
13、,v) UUv 结束。,2019年5月25日,2、 Prim过程,2019年5月25日,2019年5月25日,5.4.4 构造最小生成树的Kruskal算法,Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。 1、 Kruskal算法基本思想,2019年5月25日,2、Kruskal方法过程 对于下图所示的网，按照Kruskal方法构造最小生成树的过程如下图所示。,2019年5月25日,3、算法实现,2019年5月25日,5.5 最短路径 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和
14、达到最小。,2019年5月25日,5.5.1 从一个源点到其它各点的最短路径,1、单源点的最短路径问题： 设给定带权有向图G(Vn, En)和源点vmVn，求从vm 到G中其余各顶点的最短路径 。,2、迪杰斯特拉（Dijkstra）算法： 核心：按路径长度递增的次序产生最短路径。 即先求得只有1条边的最短路径，再求得有2条边组成的最短路径，3条边组成的最短路径。,2019年5月25日,Dijkstra逐步求解的过程,2019年5月25日,4、Dijkstra算法的实现：,2019年5月25日,5.5.2 每一对顶点之间的最短路径 -弗洛伊德算法,解决这个问题的一个办法是：每次以一个顶点为源点，
15、重复调用Dijkstra算法n次。这样，便可求得每一对顶点之间的最短路径，总的时间复杂度为O(n3)。 弗洛伊德（Floyd）提出了另一个算法。Floyd算法求解每一对顶点对间的最短路径问题仍从图的带权邻接矩阵出发，依据的是以下递推关系： D(-1)ij=edgesij D(k)ij=MinD(k-1)ij, D(k-1) ik+ D(k-1) kj 0kn-1 其中，二维数组edges存放的是带权图的邻接矩阵的值，D(k)ij是从vi到vj的中间顶点的个数不大于k的最短路径的长度，因此，D(n-1)ij是从vi到vj最短路径的长度。,2019年5月25日,5.6.1 有向无环图的概念,下图给出了有向树、 DAG图和有向图的例子。,5.6 有向无环图及其应用,2019年5月25日,(1) 有向无环图是描述含有公共子式的表达式的有效工具： 例如下述表达式： (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第六章讨论的二叉树来表示，如下图所示。,2019年5月25日,下图所示为表示同一表达式的有向无环图。,2019年5月25日,5.6.2 AOV网与拓扑排序,1AOV网 (顶点表示活动的网) (1) AOV概念：顶点表示活动，弧表示活动之间存在的制
