《《数据结构（第二版）》课件 包振宇 第六章 图》由会员分享，可在线阅读，更多相关《《数据结构（第二版）》课件 包振宇 第六章 图（40页珍藏版）》请在金锄头文库上搜索。
1、第六章 图,本章内容,6.1图的定义与术语 6.2图的存储结构 6.3图的遍历 6.4最小代价生成树 6.5*求最短路径 6.6 拓扑排序 6.7 拓扑排序,6.1图的定义与术语,6.1.1定义： 1、图G由两个集合V和E组成，记作G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常V（G）和E(G)分别表示G的顶点的集合边的集合，E（G）也可以为空集，若E（G）为空，则图G只有点而没有边。 2、在图G中，如果代表边的顶点偶对是无序的，则称G为无向图。把无向图中代表边的无序对用括号括起来，用以表示一条无向边，例（Vi, Vj）表示顶点Vi, Vj的一条
2、无向边，显然（Vi, Vj）和（Vj,Vi）所代表的是同一条边。 3、若图G中表示边的顶点偶对是有序的，则称G为有向图。有向图中的边又称为弧，用一对尖括把有序偶对括起来，表示一条有向边，例：表示从顶点Vi到Vj的一条弧，顶点Vi称为的尾,Vj为的头，用由尾指向头的箭头形象表示一条弧。可见和是两条不同的弧。,例6.1,一个简单无向图其顶点集合与边集合如下： V（G1）=V1，V2，V3，V4 E（G1）=（V1，V2），（V1，V3），（V1，V4），（V2，V3），（V3，V4） 则图例为图6-1。,例6.2,例6.2：有一有向图其顶点集合与边集合如下： V（G2）=V1，V2，V3，V4 E
3、（G2）=,V4V1V2V3 则图例为图6-2。,6.1.2术语,1、稀疏图与稠密图 具有n个顶点的无向图，边的最大数目是n(n-1)/2，有n(n-1)/2条边的无向图，称为无向完全图（如图6-3）。与之对应的有向完全图，则有n(n-1)条边（如图6-4）。n(n-1)是n个顶点的有向图的最大边数，在n个顶点的图中，当边数enlog2n时，图G称为稀疏图，否则称为稠密图。 2、权与网 在实际应用中，图的边往往与具有一定意义的数据相关，即每一条边附有一个对应的数，这种与边相关的数称为权，权可以表示从一顶点到另一个顶点的距离或花费的代价，我们称边带有权的图为网。 3、子图 假设有两个图G=（V，
4、E）和图G=（V，E），若满足条件V（G）V（G），并且E（G）E（G），则称G为G的子图。,示例,有向完全图 子图,v2,v3,v4,v1,v1,v2,v2,v3,v3,v4,v4,v1,术语（续）,4、邻接点：在图G中，若（Vi，Vj）是E（G）中的一条边，则称顶点Vi和Vj是互为邻接点。例上图G中V1,V2互为邻接点。 5、路径与回路 在图G中，顶点Vp到顶点Vq的一条路径是顶点序列（Vp，Vi1,Vi2,Vin,Vq）,且（Vp,Vi1）,(Vi1,Vi2),(Vin,Vq)属于E（G）。如果G是有向图，则路径也是有向的，由E（G）中的边,组成，路径的长度是指在这条路径上边的数目。在一
5、条路径中，除了第一顶点和最后一顶点之外，其它顶点都不同的路径，称为简单路径。第一顶点与最后一顶点相同的简单路径，称为回路或环。,术语（续）,6、连通图和强连通图 在无向图中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若V（G）中每一对不同顶点Vi和Vj都连通，则称G是连通图，在无向图中，极大的连通子图，称为它的连通分量。在有向图中，若对于V（G）中的每一对不同顶点Vi,Vj都存在以Vi到Vj以及Vj到Vi的路径，则称图G是强连通图，有向图中极大的强连通子图称为它的强连通分量。,示例,连通分量 强连通,A,V1,B,V2,C,V3,D,E,F,H,G,I,L,J,K,术语（续）,7、生成树
6、一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的n-1条边，如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有第二条路径。一棵有n个顶点的生成树有且仅有n-1 条边，如果一个有n个顶点和小于n-1条边则是非连通图，如果它多于n-1条边，如果它多于n-1条边，则一定有环。注意有n-1条边的图不一定是生成树。 8、度、入度和出度 在无向图中，顶点的具有的边的数目称该顶点的度，在有向图中以某顶点为头（终点）的边的数目，称为该顶点的入度以某顶点为尾（始点）的边的数目，称为该顶点的出度。一个顶点的入度与出度之和为该顶点的度。假设无向图G中有n
7、个顶点，e条边，每个顶点的度为di（1in），则e= 。,例 6-4,例 6-5,例6.5: 图6-11中A的度为：4; 图6-13中V4的入度为：2，V4的出度为1, V4的度为：3。,6.2图的存储结构,6.2.1邻接矩阵 图的邻接矩阵是反映顶点间邻接关系的矩阵，设G=（V，E），是具有n(n1)个顶点的图，G的邻接矩阵M是一个n列的矩阵，若有或E,则Mij=1，否则Mij=0。由邻接矩阵的定义知，无向图的邻接矩阵是对称的，有向图的邻接矩阵就不一定对称。从邻接矩阵很容易判定图中两顶点是否邻接，并方便地求各顶点的度。对于无向图，其邻接矩阵第i行元素的和即为顶点Vi的度。对于有向图，其邻接矩阵
8、的第i行元素之和为顶点Vi的出度，而邻接矩阵的第j列元素之和为顶点Vj的入度。 如果图G=（V，E）是一个网，若（Vi,Vj）或属于E，则邻接矩阵中的元素Mij为（Vi,Vj）或上的权，这里约定所有的权均不小于0。若（Vi,Vj）或不属于E，则Mij为无穷大或为零或为大于图中任何数值的实数。 若N个顶点的图G用邻接矩阵表示，则数据类型可定义为： #define N 30; /*图中最多顶点数*/ typedef int Graphnn; 若G为网，则相应的类型应定义为： typedef float GraphNetnn;,邻接矩阵示例,例6.6,6.2.2邻接表,在图的邻接表表示中，为图的每个
9、顶点建立一个链表且第i个链表中的结点代表与顶点Vi相关联的一条边或由顶点Vi出发的一条弧。有N个顶点的图，需N个链表来表示，这N个链表的头指针通常按顺序线性表方式存储。在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度；在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。,例 6-7,6.3图的遍历,6. 3.1深度优先搜索：（DFS） 遍历过程如下：首先选定一个出发顶点V，并访问；接着选择一个与V相邻并且未被访问过的顶点W访问之，再以W开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都已被访问过的顶点时，就从最近所访问的顶点开始依次回退，直至退回到某个顶点。若尚有未
10、曾访问过的邻接顶点，再以该邻接顶点开始继续进行深度优先遍历。上述过程在两种可能情况下终止：所有顶点都已被访问，或从任一个已被访问过的顶点出发，再也无法到达未曾访问过的顶点。 对于无向图，如果图是连通的，那么按深度优先搜索方法遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是不连通的。,举例,在无向图6-22中从顶点3开始，可得一遍历序列为：3 0 1 2 4 在有向图6-23中从顶点3开始，可得一遍历序列为：3 4 1 0 2,6.3.2广度优先搜索（BFS),遍历过程：首先访问出发顶点V，然后访问与顶点V邻接的全部未被访问过的顶点W0,W1,Wk-1
11、;接着再依次访问与顶点W0,W1,Wk-1邻接的全部未被访问过的顶点。依次类推，直至图中所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。 如前图6-22从顶点3开始广度优先搜索得：3，0，2，4，1；图6-23从顶点3出发得3，4，1，2，0。 由上述过程得知，若有顶点V在顶点W前被访问，则对与相邻的顶点的访问应先于只与W相邻的那些顶点的访问。因此需要一个队列来存放被访问过的顶点，以便按顶点的访问顺序依次访问与这些顶点相邻接的顶点。,6.4最小代价生成树,6.4.1概念： 1、设（，）是一个连通图的无向图，若1是包含中所有顶点的一个无回路的连通子图，则称G1为的一棵生成
12、树。从的任一顶点出发进行一次深度优先或广度优先搜索遍历，由遍历过程中走过的边的集合和访问的顶点集合构成的子图是一个连通子图，这就是图的一棵生成树。 2、含有n个顶点的连通图的生成树有n个顶点和n条边。对一个带权的图（网），在一棵生成树中各边的权值辶和称为这棵生成树的代价。一个图可以有许多不同的生成树，其中代价最小的生成树称为最小代价生成树。,举 例 6.8,6.4.2 PRIM算法,设已知G=（V，E）是一个带权连通无向图，顶点V=0，1，2,n-1。设U是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时，U只含一个出发顶点。设T是构造生成树过程中已被考虑在生成树上的边的集合，初始时T为
13、空。如果边（i,j）是具有最小代价，且i在V中，j在V-U中，那么最小代价生成树应包含边（i，j）。把j加到U中，把（i, j）加到T中。重复上述过程，直到U等于V为止。这时T即为最小代价生成树的边的集合。 设用邻接矩阵表示图，为便于程序处理，还需进一步引入一些辅助变量。数组closest 用来存放顶点号，数组lowcost 用来存放代价。数组lowcost 存放U中顶点到V-U是顶点的最小代价。若lowcosti=0,表明顶点i已在U中；若0lowcosti，则顶点i在V-U中，并且顶点closesti在U中，边（closesti，j）是U中与顶点i邻接的边中代价最小的边，其代价为lowco
14、sti；若lowcosti=，则表示closesti与顶点i辶间没有边。,6.5*求最短路径,6.5.1求从某个顶点到其他顶点的最短路径 Dijkstra提出了一个按路径长度不减次序产生最短路径的算法。其基本思想是：记指定的某顶点为V，把图中顶点集合V分成两组，以已求出最短路径的顶点集合为第一组，记为S；其余尚未确定最短路径的顶点集合为第二组。按最短路径长度递增次序逐个地把第二组中的顶点移入S中，直至从指定顶点出发可以到达的顶点都在S中。在这过程中，需始终保持从V到S中各个的最短路径长度都不大于从V到第二组的任何顶点的最短路径长度。另外，为便于程序处理，需为每个顶点保存一个距离。S中的顶点的距
15、离就是从V到此顶点的最短路径长度，第二组中的顶点的距离就是从V到此顶点的只包括以S中的顶点为中间顶点的那部分还不完整的最短路径长度。,6.5.2求每一对顶点间的最短路径,着哩介绍由Floyd提出的求每一对顶点辶间最短路径的方法。设图G=（V，E）是有n个顶点的有向图，顶点集合V=0，1，2，n-1。图用邻接矩阵M 表示。Floyd算法的基本思想是递推地产生一个矩阵序列A0，A1，A2，An的过程就是允许逐步越来越多的顶点作为路径的中间顶点 ，直到为全部路径都找到了所有的中间顶点，所有的最短路径也就全部求出，算法就此结束。,6.6 拓扑排序,设S是一个集合,R是S上的一个关系,若S中的元素a,b有(a,b)R,则称a是b关于R的前驱， b是 a关于R的后继。若对S中的元素a,b,c有（a，b）R，（b,c）R,则（a,c）R,就称R是S上的一传递关系。若对S中的任一元素，a都有(a,a)R，则R是S上的一个自反关系；反之对S中的任一元素a，都不存在(a,a)R，则称R是S上的一个非自反关系；若S上的一个关系R是传递的并且是非自反的，则称R是S上的一个半序关系。在一个具有半序关系，R的有限集合中，至少有一个元素没有前驱，也至少有一个元素没有后继。 设R是集合S上的一个半序关系，A=a0,a1,an-1是S中的一个序列，且为（ ai,aj）R 有ij,则称A是对于R的一个
