《数据结构与算法 第3版 教学课件 ppt 作者 张小莉 第5章 图结构》由会员分享，可在线阅读，更多相关《数据结构与算法 第3版 教学课件 ppt 作者 张小莉 第5章 图结构（68页珍藏版）》请在金锄头文库上搜索。
1、第5章 图结构,2019年5月19日,教学内容： 图的基本概念、图的存储方法、图的遍历、生成树和最小生成树、有向无环图及其应用、最短路径 教学目的： 理解图的基本概念及术语；掌握图的存储方法；熟练掌握图的两种遍历的算法思想、步骤；理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。 教学重点： 图的定义及其含义；图的邻接矩阵和邻接表存储方法；图的按深度优先搜索遍历和按广度优先搜索遍历方法；生成树和最小生成树的概念；Prim算法思想构造最小生成树按Prim算法思想；有向无环图的应用。 教学难点： 正确理解与区别图的常用术语；区别图的两种存储结构
2、的不同点及其应用场合；关键路径的算法思想；最短路径的算法思想。,2019年5月19日,5.1 引言,5.1.1 问题的提出 问题1：寻求走迷宫问题的解，迷宫可表示成图，求解即为寻求满足某种要求的从迷宫的入口结点到迷宫的出口结点的路径。 问题2：从公园入口处寻找一条参观某个动物的最短路径。 问题3：在几个村落之间铺设通讯线路，如何铺设最省钱。 问题4：计算机科学与技术专业的大学生，本科四年需要学习公共基础课、专业基础课、专业课几十门，每门课程都可能有先修课程的要求，如何合理安排课程的教学顺序，使学生能够顺利完成学业。 。,2019年5月19日,5.1.2 图的定义和术语,1图的定义,2019年5
3、月19日,2.图的相关术语 无向图 有向图 例：右图是一个有向图G2。 表示为： G2=(V2,E2) V2=v1,v2,v3,v4 E2=,2019年5月19日,(3) 邻接点、邻接边 (4) 完全图 (5) 稠密图、稀疏图 (6) 顶点的度、入度、出度 (7) 边的权、网图 (8) 路径和路径长度 (9) 回路、简单路径、简单回路 (10) 子图 (11) 连通的、连通图、连通分量 (12) 强连通图、强连通分量 (13) 连通图（或子图）的生成树 (14) 非连通图的生成森林,2019年5月19日,5.1.3 图的基本操作,(1) CreatGraph(G)：建立图G的存储。 (2) D
4、estroyGraph(G)：释放图G占用的存储空间。 (3) GetVex(G, v)：在图G中找到顶点v，并返回顶点v的相关信息。 (4) PutVex(G, v, value)：在图G中找到顶点v，并将value值赋给 顶点v。 (5) InsertVex(G, v)：在图G中增添新顶点v。 (6) DeleteVex(G, v)：在图G中，删除顶点v以及所有和顶点v相关联的边或弧。 (7) InsertArc(G, v, w)：在图G中增添一条从顶点v到顶点w的边或弧。,2019年5月19日,(8) DeleteArc(G, v, w)：在图G中删除一条从顶点v到顶点w的边或弧。 (9
5、) Traverse(G, v)：在图G中，从顶点v出发遍历图G。 (10) LocateVex(G, u)：在图G中找到顶点u，返回该顶点在图中存储位置。 (11) FirstAdjVex(G, v)：在图G中，返回v的第一个邻接点。若顶点在G中没有邻接点，则返回“空”。 (13) NextAdjVex(G, v, w)：在图G中，返回v的（相对于w的）下一个邻接点。若w是v的最后一个邻接点，则返回“空”。,2019年5月19日,5.2.1 邻接矩阵,1.邻接矩阵的存储思想 (1) 图中顶点顺序存储； (2) 用一个n*n矩阵（设图有n个顶点）来存储任意两个顶点之间边的信息，也就是各顶点之间
6、的邻接关系。,其中，wij表示边(vi,vj)或上的权值；表示一个计算机允许的、大于所有边上权值的数。,若G是带权图，则邻接矩阵可定义为：,5.2 图的存储方法,2019年5月19日,用邻接矩阵表示法表示的无向图和网图如下图所示。,2019年5月19日,2.邻接矩阵的表示,#define MaxVertexNum /定义能存储的足够大的顶点个数 typedef char VertexType; / VertexType为顶点类型，设为字符型 typedef int EdgeType; / EdgeType为边的权值类型，设为整型 typedef struct VertexType vexsMa
7、xVertexNum; /顶点表 EdgeType dgesMaxVertexNumMaxVertexNum; /邻接矩阵 int n, e; /实际的顶点数和边数 MMGragh;,2019年5月19日,3、邻接矩阵存储方法的特点 无向图的邻接矩阵一定是一个对称矩阵。 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的度TD(vi)。 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。 用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须
8、按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。,2019年5月19日,5、建立一个有向图邻接矩阵存储的算法,2019年5月19日,5.2.2 邻接表,邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。,1、邻接表的存储思想,2019年5月19日,下图给出无向图及对应的邻接表表示。,2019年5月19日,2、邻接表的两种结点结构,2019年5月19日,3、邻接表的定义,typedef struct node int adjvex; /邻接点域 struct node *next; /指向下一个邻接点（或边）的指针域 /若要表示边
9、上信息，则应增加相关数据域info EdgeNode; /边结点 typedef struct vnode VertexType vertex; /顶点域 EdgeNode *firstedge; /第一条边的指针 VertexNode; /顶点结点 VertexNode AdjListN; /顶点结点向量,2019年5月19日,2019年5月19日,有向图的逆邻接表 若邻接表的边结点链表建立的是以vi为头的弧链表，这样的邻接表称为逆邻接表。逆邻接表便于确定顶点的入度或以顶点vi为头的弧。 下图所示为有向图G2的邻接表和逆邻接表。,2019年5月19日,图的遍历是指从图中的任一顶点出发，对图中
10、的所有顶点访问一次且只访问一次。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。,5.3 图的遍历,2019年5月19日,5.3.1 深度优先搜索,深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。 1、深度优先搜索的概念,2019年5月19日,以下图的无向图G5为例，进行图的深度优先搜索。 得到的顶点访问序列为： v1 v2 v4v8 v5 v3v6v7,2019年5月19日,2、图的深度优先遍历算法,2019年5月19日,5.3.2 广度优先搜索,广度优先搜索（Breadth_First Search） 遍历类似于
11、树的按层次遍历的过程。 1、广度优先搜索的概念,2019年5月19日,例如，得到的顶点访问序列为： v1v2 v3 v4 v5 v6 v7 v8,2019年5月19日,2、图的广度优先遍历算法,2019年5月19日,1 . 无向图的连通性 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。,5.3.3遍历图的简单应用,2019年5月19日,2019年5月19日,2. 有向图的连通性,有向图的连通性不同于
12、无向图的连通性，可分为弱连通、单侧连通和强连通。对有向图的强连通性以及强连通分量的判定，可通过对以十字链表为存储结构的有向图的深度优先搜索实现。,2019年5月19日,5.4 生成树和生成森林,5.4.1 生成树和生成森林 1.生成树和生成森林的概念,2019年5月19日,下图是连通图G5和其深度优先生成树和广度优先生成树。图中虚线为集合B(G) 中的边，实线为集合T(G)中的边。,2019年5月19日,对于非连通图，通过这样的遍历，将得到的是生成森林。例如，下图所示为一个无向图及其深度优先生成森林，它由三棵深度优先生成树组成。,2019年5月19日,2. 生成森林的构建算法,2019年5月1
13、9日,5.4.2 最小生成树,1、 最小生成树的概念,2019年5月19日,2、如何找到一个连通网络的最小生成树？,(1) MST性质：,2019年5月19日,5.4.3 构造最小生成树的Prim算法,1、Prim算法 设G(Vn, En)为一网图，其中Vn为网图中所有顶点的集合，En为网图中所有带权边的集合。,2019年5月19日,Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。 Uu1,T=; while (UV)do (u,v)minwuv|uU,vVU TT(u,v) UUv 结束。,2019年5月19日,2、 Prim过程,2019年5月19日,2019年5月
14、19日,5.4.4 构造最小生成树的Kruskal算法,Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。 1、 Kruskal算法基本思想,2019年5月19日,2、Kruskal方法过程,2019年5月19日,3、算法实现,2019年5月19日,5.5 最短路径 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。,2019年5月19日,5.5.1 从一个源点到其它各点的最短路径,1.单源点的最短路径问题,2.迪杰斯特拉（Dijkstra）算法,2019年5月19日,Dijks
15、tra逐步求解的过程,2019年5月19日,3.Dijkstra算法的实现,2019年5月19日,5.5.2 每一对顶点之间的最短路径 -弗洛伊德算法,解决这个问题的一个办法是：每次以一个顶点为源点，重复调用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,2019年5月19日,5.6.1 有向无环图的概念,5.6 有向无环图及其应用,2019年5月19日,(1) 有向无环图是描述含有公共子式的表达式的有效工具： 例如下述表达式： (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第六章讨论的二叉树来表示，如下图所示。,2019年5月19日,仔细观察该表达式，可发现有一些相同的子表达式，如(c+d)和(c+d)*e等，在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。例如下图所示为表示同一表达式的有向无环图。,2019年5月19日,5.6.2 AOV网与拓扑排序,1AOV网 (顶点表示活动的网) (1) AOV概念：
