广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案.doc

8 图8.1 图的基本概念图： 图是数据结构G(V，E)，其中V是结点的有穷非空集合，结点的偶对为边，E是边的集合。图中的结点又称为顶点。12345图8.1.1无向图与有向图：如果图中每条边都是没有方向的，则称为无向图；无向图中的边表示图中顶点的无序对，即（u , v）和（v , u）表示同一条边。如图8.1.1为一个无向图，它的顶点集和边集分别为：V（G1） 1 , 2 , 3 , 4 , 5 E（G1）(1, 2) , (1, 4) , (2, 3) , (2, 5) , (3, 4) , (3, 5)1234图8.1.2如果图中每条边都是有方向的，则称其为有向图；有向图的边表示图中顶点的有序偶对；在有向图中，箭头表示边的方向。如图8.1.2为一个有向图，该图的顶点集和边集分别为：V（G2） 1 , 2 , 3 , 4 E（G2）(1, 2) , (1, 3) , (2, 4) , (3, 2) , (4, 3) 度、入度、出度：在一个有向图中，把以结点V为终点的弧的数目称为V的入度；把以结点V为始点的弧的数目称为V的出度。 入度和出度之和为该的结点的度。 如图8.1.2中，顶点V3的入度为2，出度为1，度为3。路径 、路径长度： 图中从VS到VP 的一条路径是指一串由顶点所成的连续序列VS , Vi1 ,Vi2 , Vin , VP ，且其中 (VP , Vi1) , (Vi1 ,Vi2) , , (Vin , VP) 都是E上的边。路径上所包含边的数目称为路径长度。简单路径、简单回路：如果一条路径的顶点序列中，顶点不重复出现，则称此路径为简单路径。起点和终点相同的路径称为 回路或环。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。连通图、强连通图：在无向图G1中，若从顶点Vt到Vs有路径，则称Vt 和Vs是连通的。如果对于图中任意两个顶点都是连通的，则称G1为连通图。 在有向图G2中，如果每一对顶点Vi , Vj ， 从Vi到Vj和从Vj到Vi都存在路径，则称G2为强连通图。子图、生成子图：在图G（V，E）和图G=（V , E）中，若V V， E E，则称图G是图G的子图。若VV，E E，则子图G=（V , E）是图G的一个生成子图。 如图8.1.3所示。12345123412345图G的一个子图图G的一个生成子图【图8.1.3】连通分量、强连通分量：所谓连通分量是指一个无向图中的极大连通子图。有向图中的极大强连通分量称作强连通分量。这里“极大”的含义是：对该子图中再加入其它结点，它便不再是连通的。无向图G1G1的三个连通分量【图8.1.4】V3V4V2V1有向图G2V3V4V2V1G2的两个强连通分量生成树、生成森林：一个连通图的生成树是含有图中所有顶点的一个极小连通生成子图，首先它是原连通图的生成子图，其次它是连通的并且有最少的边数。一棵含n个顶点的生成树有且仅有n1条边，因为一个有n个顶点的图，如果少于n1条边则为非连通图，如果多于n1条边则一定有环。但有n1条边的图不一定是生成树。一个有向图的生成森林是这样一个生成子图，它由若干棵互不相交的有根有向树组成。有根有向树是这样一个有向图，它恰有一个结点的入度为零，其余结点的入度为1，并且如果略去此图中边的方向，处理成无向图后，图是连通的。G3的一棵生成树【图8.1.5】 G3ABFECDAFEBDC【图8.1.6】 一个有向图及其生成森林ABCD359116网络：若图的每条边都带有一个权，则称这种带权图为网络。通常权是具有某种实际意义的数，比如，它们可以表示两个顶点之间的距离、耗费等。 8.2 图的存储结构8.2.1 邻接矩阵1 顶点i和j之间有边（或弧）相连0 反之邻接矩阵是表示结点间相邻关系的矩阵。若G是一个具有n个结点的图，则G的邻接矩阵是如下定义的nn矩阵： A i , j = 13245【图8.2.1】 G1例如，图8.2.1的G1的邻接矩阵为A1：0 1 1 1 11 0 0 1 01 0 0 0 11 1 0 0 11 0 1 1 0A1 无向图的邻接矩阵为对称矩阵！带权的图，其邻接矩阵中值为1的元素可以用边上的权来代替。有时还可根据需要，将网的邻接矩阵中的所有的0用代替。如图8.2.2。1423563548155679【图8.2.2】 G2 5 7 4 8 9 5 6 5 3 1 A2 在实际编程中， 如何表示？ 8.2.2 邻接表邻接表是图的一种链式存储结构。为图中每一个顶点建立一个单链表，该顶点为表头，后面连接与表头结点有边相连的结点。如图8.2.3，G1、G2的邻接表分别为：234514152513411234513245G1235166123456451236548169【图8.2.3】 G28.3 图的遍历图的遍历就是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。图的遍历使实现图的其它算法的基础。和树的遍历类似，对图也有深度和宽度两种遍历，也可分别称为深度优先搜索和广度优先搜索。8.3.1 深度优先搜索深度优先搜索可以看出是树的先根序遍历的推广。假定初始状态时，图G中所有结点都未被访问过，那么从某个结点v0出发的深度优先搜索图G的递归过程可以描述为：1 访问结点v0 （对v打上已访问标记）依次从v0的未访问的邻接点出发，深度优先搜索图G直至图中与V0有路径相通的顶点都被访问到；2 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。s 请思考上述过程与连通图、非连通图的关系。【图8.3.1】请写出图8.3.1，从顶点V1 出发进行深度搜索，得到的顶点访问序列：参考答案：V1 V2 V4 V7 V3 V5 V8 V9 V6 V10 V12 V11数据结构说明：n ：顶点数W1.n,1.n：图的邻接矩阵visited1.n：顶点访问标志从Vi出发，深度优先搜索的递归过程如下：Procedure dfs( v0 : integer ); var i:integer; beginvisit( v0); 对顶点v0的某种操作，如write(v0) visitedv0:=true;for i:=1 to n do if (Wv0,i0) and (visitedi=false) then dfs(i); end;如果是一个连通图，以上过程就已经遍历全图，但我们还应考虑非连通图的情况，对整个图进行深度遍历的算法如下：Procedure traver; var i : integer;beginfor i:=1 to n do visited i :=false;for i:=1 to n do if visited i :=false then dfs( i ); end;8.3.2 广度优先搜索广度优先搜索类似于树的按层次遍历的过程。假定初始时图中所有结点都未被访问过，那么从某个结点v0出发的广度优先搜索过程可以描述为： 1访问了V0之后，依次访问V0的各个未曾被访问的邻接点然后分别从这些邻接点出发，广度搜索图G3 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。对于图8.3.1，从顶点V1 出发进行广度搜索，得到的顶点访问序列是：V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 广度搜索的过程是以V0为起始点，由近至远，依次访问和V0有路径相通且路径长度为1，2， 的顶点。为了顺次访问路径长度为2、3、 的顶点，需设 （队列 / 栈 ？）存储1、2、 的顶点。从Vi出发，进行广度搜索的过程如下：Procedure bfs( v0 : integer); var q:array 1.n of integer; front , rear , i , v : integer;beginvisit( v0); 对顶点v0的某种操作，如打印 visitedv0:=true;q1:=v0; v0入队 front:=1; rear:=1;while front0) and (visitedi=false) then begin visitedi:=true; rear:=rear+1; 入队 qrear:=i; end;end; whileend;对整个图进行广度遍历的算法如下：Procedure traver; var i : integer;beginfor i:=1 to n do visited i :=false;for i:=1 to n do if visited i :=false then bfs( i ); end;【练习8-1】从文件读入n个城市的汽车交通图，用C i , j 表示从城市i到城市j是否有直达汽车，C i , j =1 城市i到城市j有单向直达汽车0 城市i到城市j无单向直达汽车请编制程序，输出从各城市出发乘汽车（包括转车）可以到达的所有城市。输入格式 输入文件名：city.in 第1行为整数n，代表n个城市第2行到n1行为nn的矩阵C输出格式 输出文件名：city.out 第1行为城市数n 第2到n+1行：第1个整数i，后面的整数代表从第i个城市出发可直达的城市；输入输出举例输入：输出：60 0 1 0 0 00 0 0 0 1 01 0 0 0 0 10 0 0 0 0 10 1 0 0 0 00 0 0 1 0 061 3 4 62 53 1 4 64 65 26 48.4 最小代价生成树前面已经提到，一个连通图的生成树是一个极小连通子图，它包含原图的所有结点，并且有尽可能少的边。（请先复习8.1中的“生成树”及其相关概念）遍历一个连通图可以得到图的一棵生成树。图的生成树不是唯一的，采用不同的遍历方法，从不同的顶点出发，可能得到不同的生成树。如果是带权的连通图，不同的生成树会使生成树的权值总和不同。一棵生成树的权值总和称为该生成树的代价，具有最小代价的生成树称为最小代价生成树。1452631417193138491216 例如，在n个村之间修水渠，左图表示了几个村的位置，以及各村之间修水渠的长度，当然，我们希望用最少的资金，也就是选择其中n-1条水渠，既连通各个村子，又使总的长度最少。在建立最小代价生成树时，以最小代价为原则，且必须满足下列限制：(1) 只能使用原图中的边，且仅能使用n-1边；(2) 所用的边不能形成环路最小代价生成树的生成方法主要有两种：Kruskal算法和Prim算法。8.4.1 Kruskal算法基本思想：(1) 将整个图的所有边的权值从小到大排列(2) 取出权值最小者开始进行试连接，若连接结果不会造成环路则成立，否则不进行连接；14526314349161452631417193138491216 例：设E为图G的边集，则求图G的最小代价生成树的算法如下：begin side0; 最小生成树的边数初始化 while ( side ee ( j ) 则 ee( j ) ee ( i )w ( i , j ) ； 若最后得到的拓扑序列中顶点的个数小于网中顶点数n，说明网中存在环，算法终止；否则进入下一步骤。2 从汇点vn出发，令le( n ) = ee ( n )，按逆拓扑排序求其余顶点的最迟开始时间le ( j )，与拓扑排序不同的是，它查找出度为零的结点输出，删除其所有入边。请考虑一下编程技巧？3 根据ee和le的值，对每条边ak = ( vi , vj )，计算e (k) 和 l (k)： e (k ) = ee ( i ) ， l ( k ) = le ( j ) 若 l (k)e(k) = w (k) ，则ak是关键活动。另外，若网中有几条关键路径，那么单是提高一条关键路径上的关键活动的速度，还不能缩短整个工期，而必须同时提高几条关键路径上的活动速度。【练习】某施工队建造一座楼房的工序有n个，各工序的时间及相互间依赖关系已知（由文件读入），请确定其中的关键工序。输入格式： 输入文件名： build.in 第1行： （整数） n， 代表n个工序；第2行到n1行： （若干个整数） i X V1 V2 V3 i为工序序号，X为工序时间，V1 V2 V3 为工序i所依赖的先序工序输出格式：输出文件名： build.out 第1行： （整数） m， 关键工序的数目第2到第m1行： Ki，关键工序的序号输入输出举例：输入：输出：111 62 43 54 1 15 1 26 2 37 9 4 58 8 4 59 4 610 2 711 4 8 94148118.7 最短路径在交通网络中经常遇到这样的问题：两地之间是否有路可通？在已有的几条通路的情况下，哪一条最短？我们可以把交通网络表示成带权的图，结点代表城镇，边代表城镇间的公路，边上的权代表公路的长度。上述问题就是在带权图中求最短路径的问题。 最短路径问题包括：1指定的两结点之间的最短路径2某结点到其它各结点的最短路径3任意两结点之间的最短路径8.7.1 单源最短路径给定带权有向图G和源点v0，求从v0到G中其余各顶点的最短路径。【Dijkstra算法】设一有向图G，求指定出发点v0到图中所有其它结点的最短路径的算法思想如下：1 设结点集合S，存已确定最短路径的结点，初始时为空集；设结点集合U，存未确定最短路径的结点，初始时存图中的全部结点；设一维数组D，D j 存v0到vj的暂时最短路径长度，初始时除v0为0外，其余均为无穷大； 设数组T，T i 存结点vi 到v0的最短路径上最临近vi的一个前驱结点；2 选择vj，使得 D j = Min D i | viU 即在未确定最短路径的集合U中，选择一个D j 值最小的结点vj， 移进集合S。第一次移进U的是v0；3 将vj移进S后，对U中各结点的D值和T值进行修正： 如果 D j + w j , k D k （w j , k 为边( vj , vk )上的权） 则 D k D j + w j , k ， T k j即：若v0至vk的路径上加入vj 后，使路径长度比原来更短，则修改vk的D值为加入vj后v0至vk的路径长度，并且修改其前趋结点为vj ；4 重复2、