图论中的概念及重要算法.docx

1、图论中的概念及重要算法图论中的概念及重要算法常州一中 林厚从ch1、图论中的基本概念一、图的概念简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：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，

2、v2），显然（vx，vy）和（vy，vx）是两条等价的边，所以在上面E的集合中没有再出现边（v2，v1）。 如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边。把边中Vx称为起点，Vy称为终点。显然此时边与边是不同的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。图（B）表示为：V=v1，v2，v3，E=，如果两个顶点U、V之间有一条边相连，则称U、V这两个顶点是关联的。三、带权图一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的

3、图称为带权图，也称为网（络）。四、阶图中顶点的个数称为图的阶。图（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倍，有向图中的所有顶点的入度之和等于所有顶点的出度之和

4、。 定理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，若此图是无

5、向图，则(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是强连通图。Ch2、图的存储结构一、邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵，设G

6、=V，E是一个度为n的图（顶点序号分别用1，2，n表示），则G的邻接矩阵是一个n阶方阵，Gi,j的值定义如下：1或权值 当vi与vj之间有边或弧时，取值为1或权值G i，j = 0或 当vi与vj之间无边或弧时，取值为0或（无穷大）上面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 采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边（或弧），以及边上的权值，只要看Ai,j的值即可，因为可

7、以根据i,j的值随机查找存取，所以时间复杂性为O（1）。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性均为O（n）。但是，邻接矩阵表示法的空间复杂性为O（n*n），如果用来表示稀疏图，则会造成很大的空间浪费。二、边集数组表示法边集数组是利用一维数组存储图中所有边的一种图的表示方法。每个数组元素存储一条边的起点、终点和权值（如果有的话）。在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e），e为边数。这种表示方法适合那些对边依次进行处理的运算，而不适合对顶点的运算和对任意一条边的运算。从空间复杂性上讲，边集数组适合于存储稀疏图。三、邻接表表示法（链式

8、存储法）邻接表表示法是指对图中的每个顶点vi（1in）建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。为每个顶点vi（1in）建立的单链表，是表示以该顶点为起点的所有边的信息（包括一个终点（邻接点）序号、一个权值和一个链接域）。一维向量数组除了存储每个顶点的表头指针外，还要存储该顶点的编号i。图（C）的邻接表表示为：图的邻接表表示法便于查找任一顶点的关联边及邻接点，只要从表头向量中取出对应的表头指针，然后进行查找即可。由于无向图的每个顶点的单链表平均长度为2e/n，所以查找运算的时间复杂性为O(e/n)。对于有向图来说，想要查找一个顶点的后继顶点和以该顶点

9、为起点的边、包括求该顶点的出度都很容易；但要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O（n+e）。所以，对于经常查找顶点入度或以该顶点为终点的关联边的运算时，可以建立一个逆邻接表，该表中每个顶点的单链表存储的是所有以该点为终点的关联边信息。甚至还可以把邻接表和逆邻接表结合起来，构造出“十字邻接表”，此时，每个边结点的数据信息包含五个域：起点、终点、权、以该顶点为终点的关联边的链接、以该顶点为起点的关联边的链接。表头向量的结点也包括三个域：顶点编号、以该点为终点的表头指针域、以该点为起点的表头指针域。Ch3、图的遍历一、概念从图中某一顶

10、点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。后面的函授将专门讲解。这儿我们先作个介绍。二、深度优先遍历从图中某个顶点Vi出发，访问此顶点并作已访问标记，然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历，当Vi的所有邻接点都被访问过时，则退回到上一个顶点Vk，再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。如下面的左图从顶点a出发，进行深度

11、优先遍历的结果为：a，b，c，d，e，g，f；右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7。三、广度（宽度）优先遍历从图中某个顶点V0出发，访问此顶点，然后依次访问与V0邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。如上面的左图从顶点a出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g；右图从顶点V1出发，进行广度优先遍历的结果为：V1，V2，V3，V4，V

12、5，V6，V7，V8。两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。ch4、图的重要算法一、求图的最小生成树算法如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E构成一个子图G，即G=（V， E），且边集E能将图中所有顶点连通又不形成回路，则称子图G是图G的一棵生成树。同一个图可以有不同的生成树，但可以证明：n个顶点的连通图的生成树必定含有n-1条边。对于加权连通图（连通网），生成树的权即为生成树中所

13、有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如要在若干个城市之间建一个交通网，要求各个城市都能到达且造价最低，这就是一个典型的最小生成树问题。那么如何求（最小）生成树呢？求（最小）生成树可以从某个顶点采用深度优先遍历的方法，也可采用广度优先遍历的方法，分别称为深度优先生成树和广度优先生成树。上图中的图（B）和图（C）所示两棵生成树，是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树。也可以综合应用深度优先遍历和广度优先遍历的特定算法，如：Prim算法和Kruskal算法，下面我们将分别介绍。1、用Prim算法求最小生成树的思想如下

14、：（设图G的度为n，G=（V，E）设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中XS，not (YS)；将顶点Y加入集合S，边（X，Y）加入集合TE；得到最小生成树T =（S，TE）下面给出Prim算法构造图的最小生成树的具体算法框架。 从文件中读入图的邻接矩阵g； 边集数组elist初始化；For i:=1 To n-1 Do Begin elisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=

15、g1,i+1； End； 求出最小生成树的n-1条边； For k:=1 To n-1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do 查找权值最小的一条边 If elistj.weightmin Then Begin min:=elistj.weight；m:=j；End； If mk Then Begin t:=elistk；elistk:=elistm；elistm:=t；End；把权值最小的边调到第k个单元 j:=elistk.endv； j为新加入的顶点 For i:=k+1 To n-1 Do 修改未加入的边集 Begin s:=elis

16、ti.endv； w:=gj,s； If welisti.weight Then Begin elisti.weight:=w；elisti.fromv:=j；End； End； End； 输出；2、用Kruskal算法求最小生成树的思想如下：（设图G的度为n，G=（V，E）设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。Kruskal算法在实

17、现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然

18、产生回路。下面给出利用Kruskal算法构造图的最小生成树的具体算法框架。1将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序；2设数组C1.n-1用来存储最小生成树的所有边，Ci是第i次选取的可行边在排好序的elist中的下标； 设一个数组S1.n，Si都是集合，初始时Si= i 。3i:=1；获取的第i条最小生成树的边j:=1；边集数组的下标While i=n-1 Do Begin For k:=1 To n Do Begin 取出第j条边，记下两个顶点分属的集合序号 If elistj.fromv in sk Then m1:=k； If elistj.endv

19、in sk Then m2:=k； End； If m1m2 Then Begin 找到的elist第j条边满足条件，作为第i条边保留 Ci:=j； i:=i+1； sm1:=sm1+sm2；合并两个集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下条边，继续判断 End；4输出最小生成树的各边：elistCi二、求图的最短路径算法在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。求最短路径具有很高的实用价值，在各种竞赛中经

20、常遇到。一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。1、从一个顶点到其余各顶点的最短路径看上图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci的最短路径(2i6)，输出路径序列及最短路径的路程长度。对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路

21、径(1kn-2)。下面给出解决这个问题的Dijkstra算法思想。设图G用邻接矩阵的方式存储在GA中，GAi,j=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=Vi表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist1.n用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则distj等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，distj可能越来越小。再设一个与dist对应的数组path1.n用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边

22、则为空。执行时，先从 S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为distm），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的pathm中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较distm+GAm,j的distj的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替distj，同时把Vj或边（Vm，Vj）并入到pathj中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着

23、相应的最段路径。对于上图，采用Dijkstra算法找出C1到Ci之间的最短路径(2i6)的过程如下：初始时：123456Dist048maxintmaxintmaxintPathC1C1,C2C1,C3第一次：选择m=2，则S=C1,C2，计算比较dist2+GA2,j与distj的大小（3j6）123456Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：选择m=3，则S=C1,C2,C3，计算比较dist3+GA3,j与distj的大小（4j6）123456Dist04789maxintPathC1C1,C2C1,C2,C3C1,

24、C2,C4C1,C2,C3,C5第三次：选择m=4，S=C1,C2,C3,C4，计算比较dist4+GA4,j与distj的大小（5j6）123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6第四次：选择m=5，则S=C1,C2,C3,C4,C5，计算比较dist5+GA5,j与distj的大小（j=6）123456Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因为该图的度n=6，所以执行n-2=4次后结束，此时通过dist和path数组

25、可以看出：C1到C2的最短路径为：C1C2，长度为：4；C1到C3的最短路径为：C1C2C3，长度为：7；C1到C4的最短路径为：C1C2C4，长度为：8；C1到C5的最短路径为：C1C2C3C5，长度为：9；C1到C6的最短路径为：C1C2C3C5C6，长度为：13；下面给出具体的Dijkstra算法框架（注：为了实现上的方便，我们用一个一维数组s1.n代替集合S，用来保存已求得最短路径的终点集合，即如果sj=0表示顶点Vj不在集合中，反之，sj=1表示顶点Vj已在集合中）。Procedure Dijkstra(GA,dist,path,i)； 表示求Vi到图G中其余顶点的最短路径，GA为

26、图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合BeginFor j:=1 To n Do Begin 初始化 If ji Then sj:=0 Else sj:=1； distj:=GAi,j； If distjmaxint maxint为假设的一个足够大的数 Then pathj:=i+jElse pathj:= ； End；For k:=1 To n-2 Do Begin w:=maxint；m:=i； For j:=1 To n Do 求出第k个终点Vm If (sj=0) and (distjw) Then Begin m:=j；w:=distj； End；

27、 If mi Then sm:=1 else exit；若条件成立，则把Vm加入到S中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去 For j:=1 To n Do 对sj=0的更优元素作必要修改 If (sj=0) and (distm+GAm,jdistj) Then Begin Distj:=distm+GAm,j；pathj:=pathm+j； End； End；End；2、任意一对顶点之间的最短路径这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：Floyed算法，

28、它的思路简单，但时间复杂度仍然为O（n3），下面介绍Floyed算法。设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组A，A的初值等于GA。Floyed算法需要在A上进行n次运算，每次以Vk（1kn）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素Ai，j就是图G中从顶点Vi到顶点Vj的最短路径长度。再设一个二维数组P1.n,1.n，记录最短路径，其元素类型为集合类型set of 1.n。Floyed算法的具体描述如下：Procedure Floyed(GA，A，P)； Begin For i:

29、=1 To n Do 最短路径长度数组和最短路径数组初始化 For j:=1 To n Do Begin Ai,j:=GAi,j； If Ai,jmaxint Then pi,j:=i+jElse pi,j:= ； End； For k:=1 To n Do n次运算 For i:=1 To n Do For j:=1 To n Do Begin If (i=k)or(j=k)or(i=j) Then Continue； 无需计算，直接进入下一轮循环 If Ai,k+Ak,jAi,j Then Begin 找到更短路径、保存 Ai,j：= Ai,k+Ak,j； Pi,j：= Pi,k+Pk,j； End； End； End；对于上图，大家可以运用Floyed算法，手工或编程找出任意一对顶点之间的最短路径及其长度。三、拓扑排序算法在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先