图的初步.doc

Jsoi2011秋季函授讲义（B1） 9/9图的初步在我们学过的数据结构知识中，线性表是最常用的一类，不论是用数组表示还是用链表表示，线性表中的数据关系都是线性的，即除了表头元素只有后继，表尾元素只有前驱外，其余每个数据元素都有且仅有一个前驱和一个后继，本质上是1：1的关系。在日常生活和程序设计竞赛中，还经常遇到一个元素有多个后继，或者有多个前驱的情况，这时，我们就要用到另外两种常见的数据结构：树和图。树这种结构有着明显的层次关系，每个元素只有一个前驱，但有多个后继，本质上是1：N的关系。而图这种数据结构之间的关系是任意的，即每个元素的前驱和后继个数是不定的，本质上是M：N的关系，下面我们就介绍图。第一节 图的基本概念图论研究的问题源远流长。18世纪著名的柯尼斯堡七桥问题就是一个典型有趣的问题，它的意思是说，有两条河把一座城市分成了四部分，如图5_1中的左图，C、D为两岸，A、B为河中的两个孤岛，在A、B、C、D之间有7座桥相连。有人提出了这样一个有趣的问题：能否从A、B、C、D任一地出发，恰好经过每座桥一次，最后回到出发地？图5_1这个问题看起来并不复杂，但当时谁也解决不了这个问题。直到1736年，著名数学家欧拉首先解决了这个问题，他用4个抽象的点A、B、C、D分别表示陆地，而陆地之间的每一座桥抽象成点与点之间的一条边，如图5_1中的右图，这样七桥问题就演变成了在一个图中能否从任一点出发经过每条边一次，最后返回到起点？本题的答案是否定的，因为对于每一个顶点，不论如何经过，必须有一条进路和一条出路，即与每一个顶点相邻的边（关联边）必须是偶数条，而此图中所有点都只有奇数条关联边。这就是著名的“欧拉问题”或“图的一笔画问题”，从此也开创了图论研究。下面结合图5_2先给出图论中的一些基本概念。图5_2一、 图的概念简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E），V是点（称为“顶点”）的非空有限集合，E是线（称为“边”）的集合，边一般用（vx，vy）表示，其中vx，vy属于V。图（A）共有4个顶点、5条边，表示为：V=v1，v2，v3，v4，E=（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v4）二、 无向图和有向图如果边是没有方向的，称此图为“无向图”，如图（A）和图（C），用一对圆括号表示无向边，如图（A）中的边（v1，v2），显然（vx，vy）和（vy，vx）是两条等价的边，所以在上面E的集合中没有再出现边（v2，v1）。 如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边。把边中Vx称为起点，Vy称为终点。显然此时边与边是不同的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。图（B）表示为：V=v1，v2，v3，E=，如果两个顶点U、V之间有一条边相连，则称U、V这两个顶点是关联的。三、 带权图一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的图称为带权图，也称为网（络）。四、 阶图中顶点的个数称为图的阶。图（A）、图（B）、图（C）的阶分别为4、3、5。五、 度图中与某个顶点相关联的边的数目，称为该顶点的度。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。图（A）中顶点v1，v2是奇点，v3，v4是偶点。在有向图中，把以顶点V为终点的边的数目称为顶点V的入度，把以顶点U为起点的边的数目称为顶点U的出度，出度为0的顶点称为终端顶点。如图（B）中顶点v1的入度是0、出度是2，v2的入度是2、出度是1，v3的入度是2、出度是1，没有终端顶点。 定理1：无向图中所有顶点的度之和等于边数的2倍，有向图中的所有顶点的入度之和等于所有顶点的出度之和。 定理2：任意一个无向图一定有偶数个(或0个)奇点。六、 完全图若无向图中的任意两个顶点之间都存在着一条边，有向图中的任意两个顶点之间都存在着方向相反的两条边，则称此图为完全图。n阶完全有向图含有n*(n-1)条边，n阶完全无向图含有 n*(n-1)/2条边，当一个图接近完全图时，称为稠密图；相反，当一个图的边很少时，称为稀疏图。七、 子图设有两个图G =（V，E）和G=（V，E），若V是V的子集，E是E的子集，则称G为G的子图。八、 路（径）在一个G =（V，E）的图中，从顶点v到顶点v的一条路径是一个顶点序列vi0，vi1，vi2，, vim，其中 vi0 = v， vim = v，若此图是无向图，则(vij-1，vij)E，1jm；若此图是有向图，则E，1jm。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路径，顶点v和顶点v相同的路径称为回路（或环）。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路（或简单环）。九、连通图在无向图G中，如果从顶点U到顶点V有路径，则称U和V是连通的。如果对于图G中的任意两个顶点U和V都是连通的，则称图G是连通图，否则称为非连通图。在有向图G中，如果对于任意两个顶点U和V，从U到V和从V到U都存在路径，则称图G是强连通图。第二节 图的存储结构一、 邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵，设G=V，E是一个度为n的图（顶点序号分别用1，2，n表示），则G的邻接矩阵是一个n阶方阵，Gi,j的值定义如下：1或权值 当vi与vj之间有边或弧时，取值为1或权值G i，j = 0或 当vi与vj之间无边或弧时，取值为0或（无穷大）图5_2中的3个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0 1 1 G（B）= 0 0 1 G（C）= 5 2 6 1 1 0 0 0 1 0 8 2 10 4 1 1 0 0 10 11 3 6 4 11 我们发现：无向图的邻接矩阵是对称的。相应的数据结构可以定义为： Const n=20；max=10000；对于带权图把max看成 Type g=Array1.n,1.n Of 0.1；对于带权图可以用Integer、Real等下面给出带权无向图的邻接矩阵建立过程： For i:=1 To n Do 初试化For j:=1 To n Do gi,j: =max； 对于不带权的图gi,j: =0 Readln(e)； 读入边的数目 For k:= 1 To e DoBegin Read(i,j,w)； 读入两个顶点序号及权值 gi,j:=w； 对于不带权的图gi,j: =1 gj,i:=w； 无向图的对称性End；采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边（或弧），以及边上的权值，只要看Ai,j的值即可，因为可以根据i,j的值随机查找存取，所以时间复杂性为O（1）。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性均为O（n）。但是，邻接矩阵表示法的空间复杂性为O（n*n），如果用来表示稀疏图，则会造成很大的空间浪费。二、边集数组表示法边集数组是利用一维数组存储图中所有边的一种图的表示方法。每个数组元素存储一条边的起点、终点和权值（如果有的话）。在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e），e为边数。这种表示方法适合那些对边依次进行处理的运算，而不适合对顶点的运算和对任意一条边的运算。从空间复杂性上讲，边集数组适合于存储稀疏图。图5_2中的图（C）用边集数组表示如表5_1。表5_1边数12345678起点11122334终点23535455权5832610411对于n个顶点、e条边的图G，用边集数组描述的数据结构如下：Const n=10；e=30；Type node=Record fromv,endv:1.n； 起点、终点 weight:Integer； 权值 End；Var edgelist=Array1.e Of node；三、邻接表表示法（链式存储法）邻接表表示法是指对图中的每个顶点vi（1in）建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。为每个顶点vi（1in）建立的单链表，是表示以该顶点为起点的所有边的信息（包括一个终点（邻接点）序号、一个权值和一个链接域）。一维向量数组除了存储每个顶点的表头指针外，还要存储该顶点的编号i。图5_2中的图（C）的邻接表表示为图5_3：图5_3相应的数据结构描述为：Const n=10；e=20； n为顶点数，e为边数Type edge=edgenode； edgenode=Record 边结点信息 adj:1.n； 边的终点（链接点） weight:Integer； 该边上的权、无权图可以省去next:edge； 指向下一条边的链接End；vex=Record 表头结点，包括一个起点信息和一个链接 data:Integer； 起点数据类型 link:edge； 指向下个顶点的链接信息End；Var adjlist=Array1.n Of vex；n个顶点的邻接表下面给出有向图邻接表的建立过程：Procedure createlist(Var g:adjlist)； Var s:edgenode；BeginRead(n,e)； n为顶点数，e为边数For i:=1 To n Do Begin Read(gi.data)； 读入顶点信息表 gi.link:=nil； 表头指针初始化 End；For k:= 1 To e Do 建立邻接表 Begin Read(i,j,w)； 读入一条边的起点、终点及权值 New(s)； s.adj：=j； 新结点赋值 s.weight:=w； s.next:=gi.link； gi.link:=s； 把新结点插入到vi邻接表的表头 End； End；图的邻接表表示法便于查找任一顶点的关联边及邻接点，只要从表头向量中取出对应的表头指针，然后进行查找即可。由于无向图的每个顶点的单链表平均长度为2e/n，所以查找运算的时间复杂性为O(e/n)。对于有向图来说，想要查找一个顶点的后继顶点和以该顶点为起点的边、包括求该顶点的出度都很容易；但要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O（n+e）。所以，对于经常查找顶点入度或以该顶点为终点的关联边的运算时，可以建立一个逆邻接表，该表中每个顶点的单链表存储的是所有以该点为终点的关联边信息。甚至还可以把邻接表和逆邻接表结合起来，构造出“十字邻接表”，此时，每个边结点的数据信息包含五个域：起点、终点、权、以该顶点为终点的关联边的链接、以该顶点为起点的关联边的链接。表头向量的结点也包括三个域：顶点编号、以该点为终点的表头指针域、以该点为起点的表头指针域。第三节 图的遍历一、 概念从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。二、深度优先遍历从图中某个顶点Vi出发，访问此顶点并作已访问标记，然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历，当Vi的所有邻接点都被访问过时，则退回到上一个顶点Vk，再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。如图5_4中的左图从顶点a出发，进行深度优先遍历的结果为：a，b，c，d，e，g，f；图5_4中的右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7。图5_4对于一个连通图，深度优先遍历的递归过程如下（对于非连通图，要多次调用本过程）：Procedure dfs(i:1.n)； 图用邻接表存储，其它存储方式只要对本过程稍作修改 Begin Write(gi.v)； 输出最简单的访问方式Visitedi:=True；p:=gi.link；While pNil Do Begin j：=p.adj； j为i的一个后继If Not Visitedj Then dfs(j)； 深度、递归 p:=p.next； p为i的下一个后继 End； End；三、广度（宽度）优先遍历从图中某个顶点V0出发，访问此顶点，然后依次访问与V0邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。如图5_4中的左图从顶点a出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g；图5_4中的右图从顶点V1出发，进行广度优先遍历的结果为：V1，V2，V3，V4，V5，V6，V7，V8。两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。下面是广度优先遍历的过程：Procedure bfs(i:1.n)； 图用邻接表g表示 Begin Create(q)； 过程：建队列，并初始化 Write(gi.v)； 访问Vi Visitedi:=true； 记下已访问标记 Push(q,i)； 过程：进队列 While Not empty(q) Do 广度优先遍历，直到队列空为止， Begin 表示所有顶点都已被访问过 i:=pop(q)； 过程：取顶点 p:=gi.link； 取边表指针 While pNil Do 还有后继顶点 Begin If Not visitedp.adj Then Begin Write(gp.adj.v)； 访问当前顶点 Visitedp.adj:=True； Push(q,p.adj)；