《[IT认证]第7章数据结构.ppt》由会员分享，可在线阅读，更多相关《[IT认证]第7章数据结构.ppt（37页珍藏版）》请在三一办公上搜索。
1、2,第7章 图,学习目标与要求：了解图的定义和相关术语。熟练掌握图的邻接矩阵和邻接链表表示。熟练掌握图的两种遍历方式：深度优先搜索和广度优先搜索。熟练掌握求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。熟练掌握求单源最短路径的迪杰斯特拉算法，了解求每对顶点间最短路径的弗洛伊德算法。熟练掌握求拓扑序列的方法。,3,7.1 图的定义和术语,7.1.1 图的引例图状结构较树形结构来说是一种更一般的非线性结构，它可以用来表示数据对象之间的任意关系，因此在现实生活中应用也更加广泛。把每个城市表示成一个结点，每对结点之间的边表示它们之间存在通信线路，边上的数值表示通信线路的造价，得到如图7.1所示的图
2、。,4,7.1.2 图的定义,1.图2.无向图3.有向图,5,7.1.3 图的基本术语,1.无向完全图2.有向完全图3.网4.邻接5.顶点的度6.子图7.路径、路长、简单路径和回路,6,7.1.3 图的基本术语,8.连通、连通图、连通分量9.强连通图和强连通分量10.生成树和生成森林,7,7.2 图的存储结构,由于图的结构比较复杂，具体采用什么存储方式，要依据具体的操作。从图的定义可知，无论采用什么存储方式，都要能够描述图的顶点信息和边或弧的信息。下面介绍两种常用的图的存储结构。,8,7.2.1 邻接矩阵,设G=(V,E)是一个具有n个顶点的图(n1)，则G的邻接矩阵是表示顶点之间邻接关系的n
3、阶方阵。该n阶方阵具有如下性质：图7.2(a)和7.2(b)所示图的邻接矩阵如图7.7(a)和图7.7(b)所示。,9,7.2.1 邻接矩阵,若G是网，则对应的n阶方阵具有如下性质：图7.1所示无向网用邻接矩阵表示如图7.8所示。,10,7.2.2 邻接链表,邻接链表是图的一种顺序存储与链式存储结合的存储方法。邻接链表的结点结构和数组的结点结构如图7.9(a)和图7.9(b)所示，邻接链表表示网，其结点结构如图7.10所示。,11,7.2.2 邻接链表,图7.2(a)和图7.2(b)所示图的邻接链表表示如图7.11(a)和图7.11(b)所示。,12,7.2.2 邻接链表,邻接链表存储图具有如
4、下特点：(1)无向图中，第i个链表中的表结点数是顶点vi的度；有向图中，第i个链表中的表结点数是顶点vi的出度。(2)若无向图有n个顶点、e条边，则邻接链表需n个存储单元和2e个表结点。有向图存储n个顶点e条边，需要n个存储单元和e个表结点。对于边很少的图，用邻接链表比用邻接矩阵要节省存储单元。(3)在邻接链表中，要确定两个顶点vi和vj之间是否有边或弧相连，需要遍历第i个或第j个单链表，不像邻接矩阵那样能方便地对顶点进行随机访问。,13,7.3 图 的 遍 历,图的遍历是对具有图状结构的数据线性化的过程。从图中任一顶点出发，访问输出图中各个顶点，并且使每个顶点仅被访问一次，这样得到顶点的一个
5、线性序列，这一过程叫做图的遍历。图的遍历是个很重要的算法，图的连通性和拓扑排序等算法都是以图的遍历算法为基础的。下面分别介绍图的两种遍历方法：深度优先搜索和广度优先搜索，这两种方法既适用于无向图也适用于有向图。,14,7.3.1 深度优先搜索,深度优先搜索(Depth First Search，DFS)遍历类似于二叉树的先序遍历，其基本思想是：初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将其标记为已访问，然后任选一个与v邻接且未被访问的顶点w访问输出并标记，再从与w邻接且未被访问的顶点z出发，进行深度优先搜索，重复这一过程，若到达某顶点不存在未被访问过的邻接顶
6、点时，则一直退回到最近被访问过的且存在未被访问过邻接顶点的那个顶点再进行深度优先搜索，直至所有与v有路径相通的顶点都被访问到，若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做深度优先搜索,15,7.3.1 深度优先搜索,对于图7.12所示的有向图其对应的邻接链表如图7.13所示,16,7.3.1 深度优先搜索,深度优先生成树或森林：由图中的全部顶点和深度优先搜索所经过的边即构成了深度优先生成树或森林。对图7.12所示有向图进行深度优先搜索得到的生成森林如图7.14所示。,17,7.3.2 广度优先搜索,广度优先搜索(Breadth First Search，BFS)类似于二叉树
7、的层次遍历。其基本思想是：初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将该顶点标记为已访问，然后依次访问输出与v邻接的未被访问的所有顶点，并标记为已访问，再分别从这些邻接点出发进行广度优先搜索，直至图中所有已被访问的顶点的邻接顶点都被访问到。若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做广度优先搜索。,18,7.3.2 广度优先搜索,下面仍以图7.12所示有向图为例，说明广度优先搜索的过程，其存储结构为图7.13所示的邻接链表。对图7.12所示有向图进行广度优先搜索得到的生成森林如图7.15所示。,19,7.4 最小生成树,对于有n个顶点的无
8、向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n-1条边。对于无向连通网，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，关于最小生成树的实际应用，在本章开始图的引例中已经给出其具体应用，即在n个城市之间建立通信网络并使总造价最低。多数算法利用了最小生成树的下述性质：设G=(V,E)是一个连通图，在E上定义一个权函数，U是顶点集V的一个非空子集，如果(u,v)是一条具有最小权值的边，其中uU，vV-U，则必存在一棵包含边(u,v)的最小生成树。,20,7.4.1 普里姆(Prim)算法,基本思想：假设G(V,E)是连通网，T(U,TE)为欲构造的最小生
9、成树。(1)初始时令U=1(即构造最小生成树时，从顶点1出发)，TE=。(2)从所有uU，vV-U的边中，选取具有最小权值的边(u,v)，将顶点v加入集合U中，将边(u,v)加入集合TE中。(3)重复(2)，直到UV为止。,21,7.4.1 普里姆(Prim)算法,图7.16(a)所示的是一个无向连通网，按照Prim算法，从顶点1出发，该网的最小生成树的产生过程如图7.16(b)图7.16(e)所示。,22,7.4.2 克鲁斯卡尔(Kruskal)算法,克鲁斯卡尔算法构造最小生成树的基本思想是：假设G(V,E)是连通网，T(U,TE)为欲构造的最小生成树。(1)初始时令UV，TE，即最小生成树
10、T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。(2)把G的边按权值升序排列。(3)从中选取权值最小边(u,v)，若(u,v)连接T中两个不同的连通分量，则将(u,v)并入T中。(4)重复(3)直到T中只有一个连通分量为止。,23,7.4.2 克鲁斯卡尔(Kruskal)算法,对于图7.16(a)所示无向连通网，按照克鲁斯卡尔算法构造最小生成树的过程如图7.17(a)图7.17(e)所示。,24,7.5 最 短 路 径,7.5.1 单源最短路径单源最短路径是指在有向网中，以某个顶点v0作为源点，从v0出发，到其余各个顶点的最短路径。图7.18是个有向网，图7.
11、19是其所对应的邻接矩阵cost，表7.1给出了对图7.18所示有向网，以1为源点，应用迪杰斯特拉算法求1到其余各顶点的最短路径的全过程及各数据结构的变化情况。,25,7.5.2 每一对顶点之间的最短路径,求每一对顶点之间的最短路径，可以通过两种方法：一是每次以图中的一个顶点作为源点，调用n次Dijkstra算法，便可求得图中每一对顶点间的最短路径。另一种方法是采用弗洛伊德(Floyd)算法，此算法比较简单，易于理解和编程。,26,7.5.2 每一对顶点之间的最短路径,图7.20是一个有向网和它的邻接矩阵存储，按照弗洛伊德算法求每对顶点间的最短路径，矩阵D和path的变化情况如图7.21所示。
12、,27,7.6 AOV网拓扑排序,7.6.1 AOV网一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其他有关子工程完成之后才能开始，为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、弧表示活动间先后关系的有向图称作AOV网(Activity On Vertex Network)。,28,7.6.1 AOV网,图
13、7.22所示的AOV网来表示这种课程安排的先后关系。,29,7.6.2 AOV网拓扑排序,一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行，活动会进入死循环，如图7.23所示是由三个顶点构成的一个回路，活动 1结束才能进行2，2结束才能进行3，由此推出1结束才能进行3，而从图中存在的弧可知3结束才能进行1，因此出现矛盾。,30,7.6.2 AOV网拓扑排序,对AOV网进行拓扑排序的方法如下：(1)从AOV网中选择一个入度为0的顶点，并且输出它。(2)从AOV网中删去该顶点和该顶点发出的全部有向边。(3)重复(1)和(2)，直到找不到入度为0的顶点
14、。此时，若网中仍有顶点没有输出，则说明AOV网中有环路。,31,7.6.2 AOV网拓扑排序,对于图7.22所示AOV网，其拓扑排序的过程如图7.24所示，得到的一个拓扑序列为(1,6,7,2,3,4,5)。,32,7.6.2 AOV网拓扑排序,拓扑排序算法的步骤为：(1)将id为0的顶点入栈。(2)从栈中弹出栈顶元素并输出，并把该顶点发出的所有有向边删去，即把它的各个邻接顶点的入度减1。(3)将新的id为0的顶点入栈。(4)重复(2)和(3)，直到栈空为止。此时若输出的顶点数小于n，则输出“有回路”；否则拓扑排序正常结束。,33,7.6.2 AOV网拓扑排序,图7.25(a)图7.25(h)
15、给出了对图7.22所示AOV网使用上述算法进行拓扑排序邻接链表及栈的变化过程。,34,7.6.2 AOV网拓扑排序,35,7.7 图 的 应 用,【例7.1】编程实现Prim算法。参见教材P162【例7.2】编程实现Dijkstra算法。参见教材P164,36,本 章 小 结,(1)图是一种非线性数据结构，图中元素存在多对多的关系，因此它的应用更加广泛，可以使用邻接矩阵和邻接链表两种存储方式来表示图中数据元素间的关系。(2)图的遍历算法是图的基本算法，使用该算法，可以判断图的连通性及求图的连通分量。另外注意体会图的遍历与二叉树的遍历的联系：图的深度优先搜索类似于二叉树的先序遍历，图的广度优先搜索类似于二叉树的层次遍历。(3)图有很多方面的具体应用，包括求最小生成树、求最短路径以及拓扑排序。求最小生成树可以使用Prim和Kruskal算法；求单源最短路径可以使用Dijsktra算法；求每对顶点间的最短路径可以使用Floyed算法；拓扑排序是在无环路有向图中进行的，通过拓扑排序可以判断有向图中是否存在环路，另外在求拓扑序列时注意拓扑序列可以不唯一。,37,习 题,一、填空题参见教材P166二、选择题三、判断题四、应用题五、算法设计题,
