[理学]数据结构第7章.ppt

2,第7章 图,学习目标与要求： 了解图的定义和相关术语。 熟练掌握图的邻接矩阵和邻接链表表示。 熟练掌握图的两种遍历方式：深度优先搜索和广度优先搜索。 熟练掌握求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。 熟练掌握求单源最短路径的迪杰斯特拉算法，了解求每对顶点间最短路径的弗洛伊德算法。 熟练掌握求拓扑序列的方法。,3,图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。,7.1 图的定义和术语,4,图是由非空的顶点集合和一个描述顶点之间关系边的有限集合组成的一种数据结构。可以用二元组定义为： G（V，E） 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。,7.1 图的定义和术语,5,G1=（V1，E1） V1v1,v2,v3,v4,v5； E1(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)。 (vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称为边。,7.1 图的定义和术语,6,G2=(V2,E2) V2=v1,v2,v3,v4 E2=, 表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。,7.1 图的定义和术语,7,假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶点到自身的边或者弧，即如果,则vivj 。对于无向图，边数e的取值范围为0n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图或无向完全图。对于有向图，弧度e的取值范围是0n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。具有enlogn条弧或者边的图称为稠密图。,7.1 图的定义和术语,8,7.1.2 图的基本术语,1邻接点 在无向图G=(V,E)中，如果存在边（vi,vj）E，则称vi和vj互为邻接点，即vi和vj相互邻接。边（vi,vj）依附于顶点vi和vj，或者称边（vi,vj）与顶点相互关联 在有向图G=(V,E)中，如果存在弧E，则称vi邻接到vj。 弧与顶点 vi和vj相互关联。,9,7.1.2 图的基本术语,2顶点的度 在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD (v)。 在有向图中： (a)一个顶点拥有的弧头的数目，称为该顶点的入度， 记为ID (v)； (b)一个顶点拥有的弧尾的数目，称为该顶点的出度， 记为OD (v)； (c)一个顶点度等于顶点的入度+出度， 即：TD (v)=ID (v)OD (v)。,10,在图7-1的G1中有： TD(v1)=2 TD(v2)=3 TD(v3)=3 TD(v4)=2 TD(v5)=2 在图7-2的G2中有： ID(v1)=1 OD(v1)=2 TD(v1)=3 ID(v2)=1 OD(v2)=0 TD(v2)=1 ID(v3)=1 OD(v3)=1 TD(v3)=2 ID(v4)=1 OD(v4)=1 TD(v4)=2,图7-1 无向图G1,图7-2 有向图G2,7.1.2 图的基本术语,11,7.1.2 图的基本术语,2顶点的度 假设顶点的个数为n，边数或弧数为e，顶点vi的度记作TD(vi),则顶点的度与弧度或者边数满足关系：,12,7.1.2 图的基本术语,3路径 在图中，从顶点vi出发经过一系列的顶点序列到达顶点vj称为从顶点vi到vj的路径。路径的长度是路径上弧或者边的数目。 在路径中，如果第一个顶点与最后一个顶点相同，则这样的路径称为回路或者环。,13,7.1.2 图的基本术语,3路径 在路径所经过的顶点序列中，如果顶点不重复出现，则称这样的路径为简单路径。 在回路中，除了第一个顶点和最后一个顶点外，如果其他顶点不重复出现，则称这样的回路为简单回路或者简单环。,14,4子图 对于图G=（V，E），G=（V，E），若存在V是V的子集 ，E是E的子集 ，则称图G是G的一个子图。,图7-3 图G1和G2的两个子图示意,7.1.2 图的基本术语,15,7.1.2 图的基本术语,5连通图和强连通图 在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图。否则，将其中的极大连通子图称为连通分量。,(a) 无向图G3 (b) G3的两个连通分量 图7-4 无向图及连通分量示意,16,5连通图和强连通图 在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图。否则，将其中的极大连通子图称为强连通分量。,V1,V3,V2,V4,图7-5 有向图G2的两个强连通分量示意,有向图G2,有向图G2 的两个连通分量,7.1.2 图的基本术语,17,6生成树 在含有n个顶点的图G中，如果G是包含n个顶点的极小连通子图，该子图只有n-1条边，这样的图称为连通图的生成树。如果在该生成树中添加一条边，则一定会在图中出现一个环。一棵包含n个顶点的生成树仅有n-1条边，如果少于n-1条边，则改图是非连通的。,7.1.2 图的基本术语,18,6生成树 图7-6为图7-4中无向图G3的生成树。,图7-6 无向图G3生成树示意图,7.1.2 图的基本术语,B,C,E,A,D,I,19,7网 如果在图的边或者弧上增加具有一定意义的数，这些数称为权，权通常表示一个顶点到另一个顶点的距离或者花费，带有权的图称为网。一个网如图所示。,图7-7 网的示意图,7.1.2 图的基本术语,20,7.2 图的存储结构,由于图的结构比较复杂，具体采用什么存储方式，要依据具体的操作。 从图的定义可知，无论采用什么存储方式，都要能够描述图的顶点信息和边或弧的信息。 下面介绍两种常用的图的存储结构。,21,7.2.1 邻接矩阵,图的邻接矩阵表示也称为数组表示，图的邻接矩阵就是利用C语言中的两个数组实现。其中一个是一维数组，用来存储图中的顶点信息；另一个是二维数组，用来存储图中的顶点之间的关系，该二维数组被称为邻接矩阵。,22,7.2.1 邻接矩阵,设G=(V, E)是一个具有n个顶点的图(n1)，则G的邻接矩阵是表示顶点之间邻接关系的n阶方阵。该n阶方阵具有如下性质：,23,7.2.1 邻接矩阵,若G是网，则对应的n阶方阵具有如下性质： 其中，wij表示边(vi,vj)或上的权 值；表示一个计算机允许的、大于所有边上权值的数。,24,无向图用邻接矩阵表示法如图7-8所示；网用邻接矩阵表示法如图7-9所示。,图7-9 网的邻接矩阵表示,图7-8 一个无向图的邻接矩阵表示,25,图的邻接矩阵具有以下性质： （1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。 （2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的度TD(vi)。 （3）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。 （4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。,7.2.1 邻接矩阵,26,7.2.2 邻接链表,邻接表是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，该方法将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。,27,在邻接表表示中有两种结点结构，如图7-10所示。 顶点域 边表头指针 邻接点域 指针域,顶点表,边表,图7-10 邻接表表示的结点结构,邻接点域,指针域,边上信息,网的边表结构,7.2.2 邻接链表,28,7.2.2 邻接链表,图7-11给出无向图对应的邻接表表示。,图7-11a 图的邻接表表示,29,7.2.2 邻接链表,图7-11给出无向图对应的邻接表表示。,图7-11b 图的邻接表表示,30,7.2.2 邻接链表,邻接链表存储图具有如下特点： (1) 无向图中，第i个链表中的表结点数是顶点vi的度；有向图中，第i个链表中的表结点数是顶点vi的出度。 (2) 若无向图有n个顶点、e条边，则邻接链表需n个存储单元和2e个表结点。有向图存储n个顶点e条边，需要n个存储单元和e个表结点。对于边很少的图，用邻接链表比用邻接矩阵要节省存储单元。 (3) 在邻接链表中，要确定两个顶点vi和vj之间是否有边或弧相连，需要遍历第i个或第j个单链表，不像邻接矩阵那样能方便地对顶点进行随机访问。,31,7.3 图 的 遍 历,图的遍历是对具有图状结构的数据线性化的过程。从图中任一顶点出发，访问输出图中各个顶点，并且使每个顶点仅被访问一次，这样得到顶点的一个线性序列，这一过程叫做图的遍历。 图的遍历是个很重要的算法，图的连通性和拓扑排序等算法都是以图的遍历算法为基础的。 下面分别介绍图的两种遍历方法：深度优先搜索和广度优先搜索，这两种方法既适用于无向图也适用于有向图。,32,7.3.1 深度优先搜索,深度优先搜索(Depth First Search，DFS)遍历类似于二叉树的先序遍历，其基本思想是： 初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将其标记为已访问，然后任选一个与v邻接且未被访问的顶点w访问输出并标记，再从与w邻接且未被访问的顶点z出发，进行深度优先搜索，重复这一过程，若到达某顶点不存在未被访问过的邻接顶点时，则一直退回到最近被访问过的且存在未被访问过邻接顶点的那个顶点再进行深度优先搜索，直至所有与v有路径相通的顶点都被访问到，若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做深度优先搜索,33,7.3.1 深度优先搜索,对于图7-12所示的有向图其对应的邻接链表如图7-13所示,得到的线性序列为1,2,4,3,5,7,6,34,7.3.1 深度优先搜索,深度优先生成树或森林：由图中的全部顶点和深度优先搜索所经过的边即构成了深度优先生成树或森林。 对图7.12所示有向图进行深度优先搜索得到的生成森林如图7.14所示。,35,7.3.2 广度优先搜索,广度优先搜索(Breadth First Search，BFS)类似于二叉树的层次遍历。 其基本思想是： 初始时将图中所有顶点标记为未被访问过，从图中某个顶点v出发，访问输出该顶点，并将该顶点标记为已访问，然后依次访问输出与v邻接的未被访问的所有顶点，并标记为已访问，再分别从这些邻接点出发进行广度优先搜索，直至图中所有已被访问的顶点的邻接顶点都被访问到。若此时图中仍有未被访问的顶点，则另选一个未被访问的顶点，开始再做广度优先搜索。,36,7.3.2 广度优先搜索,下面仍以图7.12所示有向图为例，说明广度优先搜索的过程，其存储结构为图7.13所示的邻接链表。,得到的线性序列为1,2,4,3,5,7,6,37,7.3.2 广度优先搜索,对图7.12所示有向图进行广度优先搜索得到的生成森林如图7.15所示。,38,v1 v2 v4 v8 v5 v3 v6 v7,v1v2v3v4v5v6v7 v8,39,7.4 最小生成树,最小生成树就是指在一个连通网的所有生成树中，所有边的代价之和最小的那棵生成树。代价在网中用权值表示，一个生成树的代价就是生成树各边的代价之和。 最小生成树有重要的研究意义，例如，要在n各城市建立一个交通图，就是要在n(n-1)/2条线路中选择n-1条代价最小的线路，在这里可以将各个城市看成图的顶点，城市的线路看成边。,40,7.4 最小生成树,1普里姆算法 2克鲁斯卡尔算法,41,7.4.1 普里姆(Prim)算法,基本思想：假设G(V, E)是连通网，T(U, TE)为欲构造的最小生成树。 (1)初始时令U=1(即构造最小生成树时，从顶点1出发)，TE=。 (2)从所有uU，vV-U的边中，选取具有最小权值的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合TE中。 (3)重复(2)，直到UV为止。,42,图7-16 Prim 算法构造最小生成树的过程示意图,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,(a),(b),(c),(d),(e),(f),6,8,12,14,16,17,5,15,6,6,6,6,6,8,8,8,8,8,12,12,12,14,14,5,43,7.4.2 克鲁斯卡尔(Kruskal)算法,克鲁斯卡尔算法构造最小生成树的基本思想是：假设G(V, E)是连通网，T(U, TE)为欲构造的最小生成树。 (1)初始时令UV，TE，即最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。 (2)把G的边按权值升序排列。 (3)从中选取权值最小边(u, v)，若(u, v)连接T中两个不同的连通分量，则将(u, v)并入T中。 (4)重复(3)直到T中只有一个连通分量为止。,44,图7-17 Kruskal 算法构造最小生成树的过程示意图,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,A,E,B,F,C,D,(a),(b),(c),(d),(e),(f),6,8,12,14,16,17,5,15,5,6,6,6,6,8,8,8,5,12,12,5,5,14,5,45,7.5 最 短 路 径,7.5.1 单源最短路径 单源最短路径是指在有向网中，以某个顶点v0作为源点，从v0出发，到其余各个顶点的最短路径。 图7-18是个有向网，图7.19是其所对应的邻接矩阵cost，表7.1给出了对图7.18所示有向网，以1为源点，应用迪杰斯特拉算法求1到其余各顶点的最短路径的全过程及各数据结构的变化情况。,46,表7-1,图7-19 有向网的邻接矩阵,图7-18 有向网示意图,47,7.5.2 每一对顶点之间的最短路径,求每一对顶点之间的最短路径，可以通过两种方法： 一是每次以图中的一个顶点作为源点，调用n次Dijkstra算法，便可求得图中每一对顶点间的最短路径。 另一种方法是采用弗洛伊德(Floyd)算法，此算法比较简单，易于理解和编程。,48,7.5.2 每一对顶点之间的最短路径,图7.20是一个有向网和它的邻接矩阵存储，按照弗洛伊德算法求每对顶点间的最短路径，矩阵D和path的变化情况如图7.21所示。,49,7.6 AOV网拓扑排序,7.6.1 AOV网 一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。 在整个工程中，有些子工程(活动)必须在其他有关子工程完成之后才能开始，为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、弧表示活动间先后关系的有向图称作AOV网(Activity On Vertex Network)。,50,7.6.1 AOV网,图7-22 表示课程间先后关系的AOV网,表7-2 计算机专业学生必修课程名称与代号,51,7.6.2 AOV网拓扑排序,一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行，活动会进入死循环，如图7.23所示是由三个顶点构成的一个回路，活动 1结束才能进行2，2结束才能进行3，由此推出1结束才能进行3，而从图中存在的弧可知3结束才能进行1，因此出现矛盾。,52,7.6.2 AOV网拓扑排序,对AOV网进行拓扑排序的方法如下： (1) 从AOV网中选择一个入度为0的顶点，并且输出它。 (2) 从AOV网中删去该顶点和该顶点发出的全部有向边。 (3) 重复(1)和(2)，直到找不到入度为0的顶点。 此时，若网中仍有顶点没有输出，则说明AOV网中有环路。,53,7.6.2 AOV网拓扑排序,对于图7.22所示AOV网，其拓扑排序的过程如图7.24所示，得到的一个拓扑序列为(