《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第七章 图》由会员分享，可在线阅读，更多相关《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第七章 图（20页珍藏版）》请在金锄头文库上搜索。
1、第七章 图,知识教学目标,图的有关概念和存储结构 图的遍历方法 生成树的概念和最小生成树 最短路径的概念和求解,能力培养目标,图的邻接矩阵表示法和邻接表表示法 图的遍历方法的实现 最小生成树的实现 迪杰斯特拉算法的实现,7.1 图的基本概念,7.1.1 图的定义 图（Graph）：是一种数据结构，由二个集合V和E组成，记作G=（V，E）。其中V是数据元素（顶点）的非空有限集，E是V中二元关系（边edge）的集合。树是图的特例，而线性表是树的特例。 图的每条边都是有序顶点对（即边是有方向的），则此图称为有向图。 图的每条边都是无序顶点对，若有（u ,v）E，则必有（u ,v）E，即边是无方向的，
2、则此图称为无向图。,7.1.2 图的基本术语 1. 度、入度、出度 2. 子图 3. 权 4. 连通图和强连通图 5. 连通分量和强连通分量 6. 路径、回路 7. 生成树,7.2 图的存储结构,7.2.1 邻接矩阵 1邻接矩阵的存储形式及性质 设图G=（V，E），有n个顶点，则其所对应的邻接矩阵A是按如下定义的一个二维数组：,2网的邻接矩阵 网的邻接矩阵可类似地定义为：,3图的邻接矩阵数据类型描述及运算,图的邻接矩阵数据类型可描述如下： typedef struct DataType Vn+1; int arcsn+1n+1; Graph;,【算法7.1】 无向图邻接矩阵的建立算法。 voi
3、d CreateAdj(Graph g) int i,j,k，e,n; scanf( ,【算法7.2】 有向图邻接矩阵的建立算法。 void CreateAdj(Graph g) int i,j,k，e,n; scanf( ,7.2.2 邻接表 1. 邻接表的存储形式及性质 链表中结点的类型定义为： typedef struct node int data; struct node *next; NODE; 表头结点类型定义为： typedef struct tnode int v; NODE *next; TNODE;,7.3 图的遍历,7.3.1 深度优先搜索 1) 首先访问出发点vi，并
4、将其访问标志记为已访问过，即设visitedi=1； 2) 然后依次从vi出发搜索vi的每个邻接点w，若w未曾访问过，则以w为新的出发点继续进行深度优先搜索遍历，直至图中所有和源点vi有路径相通的顶点（也称为从源点可达的顶点）均已被访问为止。 3) 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。,7.3.2 广度优先搜索,广度优先搜索遍历可以定义为： 1) 首先访问出发点v，并将其访问标志记为已访问过，即设visitedi=1； 2) 接着依次访问顶点v的所有邻接点w1，w2，wi； 3) 然后再依次访问顶点w1，w2，wi的所有
5、邻接点。 4) 如此类推，直至图中所有的顶点都被访问到。,7.4 生成树,最小生成树 对于连通的带权图（连通网）G，其生成树也是带权的。此时，把生成树T中各边的权值总和称为该树的权。 将图G的所有生成树中权值最小的生成树称为G的最小生成树，最小生成树可记为MST。,1普里姆（Prim）算法,普里姆算法的基本思想为：首先从集合V中选取任一顶点（例如取顶点v0）放入集合U中，这时Uv0,TE=NULL，然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权最小的边（u，v）（uU，vVU），将该边放入TE，并将顶点v加入集合U。重复上述操作直到UV为止。此时TE中有n-1条边，T（U
6、，TE）就是G的一棵最小生成树。,2克鲁斯卡尔（kruskal）算法,克鲁斯卡尔算法的基本思想为：将图中所有边按权值递增顺序排列，依次选取权值较小的边，但要求后面选择的边不能与前面选择的边构成回路，若构成回路，则放弃该条边，重复这个过程，n个顶点的图，选够n-1条边即可。,7.5 最短路径,7.5.1 单源点最短路径 单源点最短路径是指：给定一个出发点（源点）和一个有向网G=（V，E），求出源点到其它各顶点之间的最短路径。 为了求出最短路径，迪杰斯特拉（Dijlstra）在做了大量观察后，首先提出了按路长递增产生各顶点的最短路径算法，称之为迪杰斯特拉算法。 迪杰斯特拉算法的基本思想为：设置并逐
7、步扩充一个集合U，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-U，其中V为网中所有顶点的集合。按最短路径长度递增的实现逐个把V-U中的顶点加到U中，直到U中包含全部顶点，而V-S为U。,7.5.2 所有顶点之间的最短路径 弗洛伊德算法的基本思想：该算法仍然使用前面定义的图的邻接矩阵cost存储，同时定义一个二维数组ANN，其每一个分量Aij的值是顶点i到顶点j的最短路径。其基本思想为： 1) 初始时，对图中任意两个顶点vi和vj，如果从vi到vj存在弧，则从vi到vj存在一条长度为costij的路径，但该路径不一定时最短路径。初始化时，Aij=costij。 2) 对图中任意
8、两个顶点vi和vj之间的路径，考虑途经vk（k=0）的路径是否存在。若存在，则比较途经vk（k=0）的路径是否距离更短，较小的送入Aij。 3) 重复2）步，从vi出发，途经vk（k=1，2，n-1）的路径是否距离更短。,7.6 拓扑排序,拓扑排序的方法如下： 在AOV网中选择一个入度为0的顶点，并将其输出。 从AOV网中删除该顶点和所有以它为尾的弧。 重复1和2，直至所有顶点都被输出，或者当前AOV网中不存在入度为0的顶点为止。前一种情况表示AOV网中无回环存在，而后一种情况则说明AOV网中存在了回环。,7.7本章小结,图是一种网状型的数据结构，属于多对多的非线性结构，图中的每个结点可以有多
9、个直接前趋和直接后继。图的存储结构有邻接矩阵、邻接表等。 图的遍历包含深度优先搜索遍历和广度优先搜索遍历。对于用邻接矩阵结构存储的图，从某个给定的顶点出发的图的遍历得到的访问顶点次序是唯一的，而对于邻接表结构存储的图从某个给定的顶点出发的图的遍历得到的访问顶点次序随建立邻接表的不同而可能不同。 一个连通图的生成树含有该图的全部n各顶点和其中n-1条边（不构成回路），其中权值之和最小的生成树称为最小生成树。求最小生成树有两种不同的方法，一种是普里姆算法，另一种是克鲁斯卡尔算法。 求图的最短路径有两种，其一是单源点的最短路径，用迪杰斯特拉算法来实现；其二是所有顶点对的最短路径，用弗洛伊德算法来实现。,
