内蒙古大学《算法与数据结构》讲义12图

下载第1 2章图恭喜！你已经成功穿越了“树”的森林，下面要学习图这种数据结构。令人惊叹的是，图可以用来描述成千上万的实际问题，不过，我们仅研究其中的一小部分。本章的主要内容如下： 图的若干术语：顶点，边，邻接，关联，度，回路，路径，连通构件，生成树。 图的三种类型：无向图，有向图和加权的图。 图的常用表示方法：邻接矩阵，邻接链表和邻接压缩表。 图的标准搜索方法：宽度优先搜索和深度优先搜索。 在图中寻找路径，在无向图中寻找连通构件以及在无向连通图中寻找生成树的算法。 如何把抽象数据类型表示成一个抽象类。本章所使用的新的C + +特征是：抽象类，虚函数和虚基类。12.1 基本概念简单地说，图（g r a p h）是一个用线或边连接在一起的顶点或节点的集合。正式一点的说法是，图G= (V,E) 是一个V和E的有限集合，元素V称为顶点（vertice, 也叫作节点或点） ，元素E称为边（edge, 也叫作弧或连线） ，E中的每一条边连接V中两个不同的顶点。可以用（i，j）来表示一条边，其中i 和j 是E所连接的两个顶点。一般来说，图是由回路和边组成，如图1 2 - 1所示。在图1 2 - 1中有些边是带方向的（带箭头） ，而有些边是不带方向的。带方向的边叫有向边（ directed edge） ，而不带方向的边叫无向边（undirected edge） 。对无向边来说，(i, j) 和(j, i) 是一样的；而对有向边来说，它们是不同的。前者的方向是从i 到j，后者是从j 到i。当且仅当(i, j) 是图中的边时，顶点i 和j 是邻接的（a d j a c e n t） 。边(i, j) 关联（i n c i d e n t）于顶点i 和j。图12-1a 中的顶点1和2是邻接的，顶点1和3，1和4，2和3，3和4也是邻接的，除此之外，这个图中没有其他邻接的顶点。边（1，2）关联于顶点1和2， （2，3）关联于顶点2和3。图12-1 图有些书中用i, j 表示无向边，而用（i, j）表示有向边。还有一些书用（i, j）表示无向边，用表示有向边。本书对两种边使用同一符号（i, j） ，边有向与否可从上下文中看出。a)b)c)在有向图中，有时候对邻接和关联的概念作更精确的定义非常有用。有向边 (i, j) 是关联至（incident to）顶点j 而关联于（incident from）顶点i。顶点i 邻接至（adjacent to）顶点j，顶点j邻接于（adjacent from）顶点i。在图12-1c 的图中，顶点2邻接于顶点1，而1邻接至顶点2。边（1，2）关联于顶点1而关联至顶点2。顶点4邻接至顶点3且邻接于顶点3。边（3，4）是关联于顶点3而关联至顶点4。对于无向图来说， “至”和“于”的含义是相同的。如果使用集合的表示方法，图 1 2 - 1中的几个图可以用如下方法表示： G1 =（V1，E1） ；G2 =（V2，E2）和G3 =（V3，E3） ，其中：V1 = 1 , 2 , 3 , 4 ；E1 = ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 3 ) , ( 1 , 4 ) , ( 3 , 4 ) V2 = 1 , 2 , 3 , 4 , 5 , 6 , 7 ；E2 = ( 1 , 2 ) , ( 1 , 3 ) , ( 4 , 5 ) , ( 5 , 6 ) , ( 5 , 7 ) , ( 6 , 7 ) V3 = 1 , 2 , 3 , 4 , 5 ；E3 = ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 4 , 3 ) , ( 3 , 5 ) , ( 5 , 4 ) 如果图中所有的边都是无向边，那么该图叫作无向图（ undirected graph） ，图12-1a 和b 都是无向图。如果所有的边都是有向的，那么该图叫作有向图（ directed graph） ，图12-1c 是一个有向图。由定义知道，一个图中不可能包括同一条边的多个副本，因此，在无向图中的任意两个顶点之间，最多只能有一条边。在有向图中的任意两个顶点之间，最多只能有一条边从顶点 i 到顶点j 或从j 到i。并且一个图中不可能包含自连边（s e l f - e d g e） ，即(i,i) 类型的边，自连边也叫作环（l o o p） 。通常把无向图简称为图，有向图仍称为有向图（ d i g r a p h） 。在一些图和有向图的应用中，我们会为每条边赋予一个权或耗费，这种情况下，用术语加权有向图（ weighted graph）和加权无向图（weighted digraph）来描述所得到的数据对象。术语网络（ n e t w o r k）在这里是指一个加权有向图或加权无向图。实际上，这里定义的所有图的变化都可以看作网络的一种特殊情况一个无向（有向）图可以被看作是一个所有边具有相同权的无向（有向）网络。12.2 应用无向图，有向图和网络常常用于电子网络的分析、化合物（特别是碳氢化合物）的分子结构研究、空中航线和通信网络的描述、项目策划、遗传研究、统计、社会科学及它各种领域。这一节将用图来阐述一些实际问题。例12-1 路径问题 城市中有许多街道，每一个十字路口都可以看作图中一个顶点，邻接两个十字路口之间的每一段街道既可以看作一条，也可以看作两条有向边。如果街道是双向的，就用两条有向边。如果街道是单向的，就用一条有向边。图1 2 - 2给出了假想的街道和相应的有向图。图中有三条街道：街道1，街道2和街道3以及两条大街：大街1和大街2。十字路口用数字1到6进行编号，相应的有向图（如图12-2b所示）的顶点标号与图12-2a 给出的十字路口的标号相同。当且仅当对于每一个j（1jk） ，边（ij , ij+ 1）都在E中时，顶点序列P=i1 , i2 , ik是图或有向图G= (V, E)中一条从i1到ik的路径。当且仅当相应的有向图中顶点i 到顶点j 有一条路径时，十字路口i 到j 之间存在一条路径。在图12-2b 的有向图中，5，2，1是从5到1的一条路径，在这个有向图中，从5到4之间没有路径。简单路径是这样一条路径：除第一个和最后一个顶点以外，路径中其他所有顶点均不同。路径5,2,1 是简单路径，而2 , 5 , 2 , 1则不是。对于图或有向图的每一条边，均可以给出一个长度。路径的长度是路径上所有边的长度之和。从十字路口i 到j 的最短路径是相应网络中顶点i 到j 的最短路径。3 6 6第二部分数 据 结 构下载图12-2 街道及其相应的有向图a) 街道地图b) 有向图例12-2 生成树 设G= (V,E)是一个无向图，当且仅当G中每一对顶点之间有一条路径时，可认为G是连通的（c o n n e c t e d） 。图12-1a 中的无向图是连通的，而b 中的无向图不是。假定G是一个通信网络，V是城市的集合，E是通信链路的集合。当且仅当 G是连通的时候，V中的每一对城市之间可以通信。图12-1a 的通信网络中，城市2和4之间可以通过链路2，3，4进行通信，而图12-1b 的网络中，城市2和4不能通信。假设G是连通的，G中的有些边可能不是必需的，因此即使将它从 G中去掉，G仍然可以保持连通。在图12-1a 中，即使将边( 2 , 3 )和（1 , 4）去掉，整个图仍可以保持连通。图H是图G的子图（s u b g r a p h）的充要条件是，H的顶点和边的集合是G的顶点和边的集合的子集。环路（c y c l e）的起始节点与结束节点是同一节点。例如，图 12-1a 中，1 , 2 , 3 , 1是一个环路。没有环路的无向连通图是一棵树。一棵包含 G中所有顶点并且是G的子图的树是G的生成树（spanning tree） 。图12-1a 的生成树如图1 2 - 3所示。图12-3 图12-1a 的生成树第1 2章图3 6 7下载a)b)街道1大街1单向单向单向单向大街2街道2街道3a)b)c)f)e)d)一个n节点的连通图必须至少有n- 1条边。因此当通信网络的每条链路具有相同的建造费用时，在任意一棵生成树上建设所有的链路可以将网络建设费用减至最小，并且能保证每两个城市之间存在一条通信路径。如果链路具有不同的耗费，那么需要在一棵最小耗费生成树（生成树的耗费是所有边的耗费之和）上建立链路。图 12-4 给出了一个图和它的生成树，图12-4b 的生成树是一棵最小耗费生成树。图12-4 连通图和它的两棵生成树a) 图b) 耗费为1 0 0的生成树c) 耗费为1 2 9的生成树例12-3 翻译人员 假设你正在策划一次国际性会议，此次大会上的所有发言人都只会说英语，而参加会议的其他人说的语言是L1, L2, , Ln之一。翻译小组能够将英语与其他语言互译。现在你的任务是如何使翻译小组的人数最少。可以将这个任务转化为一个图的问题。在这个问题中有两组顶点，一组是相应的翻译人员，一组是语言 (如图1 2 - 5所示)。在翻译人员i 与语言L j 之间存在一条边的充要条件是翻译人员i 能够将英语和Lj 互译。当且仅当一条边连接翻译人员和语言时，翻译人员i 覆盖语言L i。我们需要找到能够覆盖所有语言顶点的最小翻译人员顶点子集。图1 2 - 5有一个有趣的特征：可以将顶点集合分成两个子集 A（翻译人员顶点）和 B（语言顶点） ，这样每条边在A中有一个端点，在B中有一个端点，具有这种特征的图叫作二分图（bipartite graph） 。12.3 特性设G是一个无向图，顶点 i 的度（d e g r e e）di是与顶点i 相连的边的个数。对于图 1 2 - 1 a，d1=3, d2=2, d3=3, d4= 2。3 6 8第二部分数 据 结 构下载a)b)c)图12-5 翻译人员和语言翻译人员语言特性1 设G= (V, E)是一个无向图，令| V | =n, | E | =e, di 为顶点i 的度，则1 )ni = 1di= 2e2) 0en(n- 1 ) / 2证明要证明1 )，注意到无向图中的每一条边与两个顶点相连，因此顶点的度之和等于边的数量的2倍。对于2 )，一个顶点的度是在0到n- 1之间，因此度的和在 0到n(n- 1 )之间,从1) 可知，e是在0到n(n- 1 ) / 2之间。一个具有n 个顶点，n(n- 1 ) / 2条边的图是一个完全图（ complete graph） 。图1 2 - 6给出了n= 1 , 2 , 3和4时的完全图。kn代表n 顶点的完全图。图12-6 完全图a) K1b) K2c) K3d) K4设G是一个有向图，顶点i 的入度（i n - d e g r e e）dii n是指关联至顶点i 的边的数量。顶点i 的出度（o u t - d e g r e e）dio u t是指关联于该顶点的边的数量。对于图12-1c 的有向图，d1in = 0，d1o ut= 0，d2in= 1，d2o ut= 1，d3in= 2，d3o ut= 2。特性2 设G= (V,E)是一个有向图，n 和e 的定义与特性1相同，则1) 0en(n- 1 )2 )ni= 1diin=ni= 1dio ut=e证明在练习2中，将要求完成这个特性的证明。一个n 顶点的完全有向图（complete digraph）包含n(n- 1 )条有向边，图1 2 - 7给出了n= 1 , 2 , 3和4时的完全有向图。入度和出度在无向图中可以作为度的同义词。本节提供的定义可以直接扩充到网络中。图12-7 完全有向图a) K1b) K2c) K3d) K4练习1. 对于图1 2 - 8的每一个有向图，确定下列各项：第1 2章图3 6 9下载a)b)c)d)a)b)c)d)1) 每个顶点的入度。2) 每个顶点的出度。3) 邻接于顶点2的顶点集合。4) 邻接至顶点1的顶点集合。5) 关联于顶点3的边的集合。6) 关联至顶点4的边的集合。7) 所有的有向环路和它们的长度。图12-8 有向图2. 证明特性2。3. 设G是任意无向图，证