图论2

图 论

第一节 图的基本概念

引入：柯尼斯堡七桥问题，能否从A地发出，各座桥恰好通过一次，最后回到出发地A？

结论：1736年，数学家欧拉首先解决了这个问题，由此开创了图论研究。这事实上是欧拉图的“一笔画问题”。答案是否定的，因为，对于每一个顶点，不论如何经过，必须有一条进路和一条出路，与每一个顶点相邻的线（关联边）必须是偶数条（除起点和终点外），而此图中所有点都只有奇数条关联边。在后面的应用中，我们将专门讨论这个问题。 定义：简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合，一般用（Vx，Vy）表示，其中，Vx，Vy属于V。

分类：如果边是没有方向的，称为“无向图”。表示时用一队圆括号表示，如：（Vx，Vy），（Vy，Vx），当然这两者是等价的。并且说边（Vx，Vy）依附于（相关联）顶点Vx和Vy。 如果边是带箭头的，则称为“有向图”，表示时用一队尖括号表示，此时与是不同的，如的起点为VX，终点为VY。有向图中的边又称为弧。起点称为弧头、终点称为弧尾。

相邻：若两个结点U、V之间有一条边连接，则称这两个结点U、V是关联的。 带权图：两点间不仅有连接关系，还标明了数量关系（距离、费用、时间等）。 图的阶：图中结点的个数。

结点的度：图中与结点A关联的边的数目，称为结点A的度。 入度：在有向图中，把以结点V为终点的边的数目称为V的入度； 出度：在有向图中，把以结点U为起点的边的数目称为U的出度； 奇点：度数为奇数的结点； 偶点：度数为偶数的结点；

终端结点：在有向图中，出度为0的结点；

定理1：无向图中所有结点的度数之和等于边数的2倍，有向图中的所有顶点的入度之和等于所有顶点的出度之和；

定理2：任意一个无向图一定有偶数个（或0个）奇点；

连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V是连通的。

路（径）：从一个结点出发，沿着某些边连续地移动而到达另一个指定的结点，这种依次由结点和边组成的序列，叫“路”或者“路径”。 路径长度：路径上边的数目。

简单路径：在一个路径上，各个结点都不相同，则称为简单路径。 回路：起点和终点相同的路径，称为回路，或“环”。

连通图：对于图G中的任一对不同顶点U、V，都有一条（U，V）通路，则称图G是连通的。 强连通图：在有向图G中，如果对于任意两个顶点u和v，从u到 v和从v到u都存在路径，则称图G是强连通图。

第二节 图在计算机中的表示——存储结构

一、邻接矩阵表示法

无向图

G[I，J] = 1 当I与J两个结点之间有边或弧时

= 0或∞ 当I与J两个结点之间无边或弧时，或I=J

如上图A的邻接矩阵如下：

下面给出带权无向图的邻接矩阵建立过程：

For(i=1;i<=n;i++) For(j=1;j<=n;j++)

G[i][j]=max; //对于不带权的图G[i][j]=0 Scanf(“%d”,&e); For(k=1;k<=e;k++) {

Scanf(“%d%d%d”,&I,&j,&w); G[i][j]=w; G[j][i]=w;

}

采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边，以及边上的权值，只要看G[i][j]的值即可，因为可以根据i，j的值随机查找存取，所以时间复杂度为O（1）。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂度均为O（n） .

但是，邻接矩阵表示法的空间复杂度为O（n*n），如果用来表示稀疏图，则会造成很大的空间浪费。

二、邻接表表示法（链式存储法）

邻接表表示法是指对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。为每个顶点建立的单链表，是表示以该顶点为起点的所有边的信息（包括一个终点（邻接点）序号、一个权值和一个链接域）。一维向量数组除了存储每个顶点的表头指针外，还要存储该顶点的编号i。

以上图（A）、图（B）的邻接表分别如下，请大家自己画出图（C）的邻接表。

第三节 图的基本处理——遍历

1、概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算称图的遍历。为了避免重复访问某个结点，可以设一个标志数组visited[I]，未访问时值为FALSE，访问一次后就改为TRUE。 2、分类：深度优先遍历和广度优先遍历。

3、深度优先遍历：类似于树的先序遍历，从图中某个结点V0出发，访问此结点，然后依次访问从V0的未被访问的邻接点出发进行深度优先遍历，直到图中所有和V0有路径相通的结点均被访问到。若此时图中尚有结点未被访问，则另选图中一个未被访问的结点V1作为起点，重复上述过程，直至图中所有结点都被访问到为止。 如下面两个图的深度优先遍历结果分别为：a，b，c，d，e，g，f

V1，V2，V4，V8，V5，V3，V6，V7

4、广度优先遍历：从图中某个结点V0出发，访问此结点，然后依次访问与V0邻接的、未被访问过的所有结点，然后再分别从这些结点出发进行广度优先遍历，直到图中所有被访问过的结点的相邻结点都被访问到。若此时图中还有结点尚未被访问，则另选图中一个未被访问过的结点作为起点，重复上述过程，直到图中所有结点都被访问到为止。如上面两个图的广度优先遍历结果分别为： a，b，d，e，f，c，g

V1，V2，V3，V4，V5，V6，V7，V8

与深度优先不同的是，深度优先实际上是尽可能地走“顶点表”；而广度优先是尽可能沿结点的“边表”进行访问，然后再沿边表对应结点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度遍历。

第四节 求图的最小生成树算法

同一个图可以有不同的生成树，但可以证明：n个顶点的连通图的生成树必定含有n-1条边。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。

求图的最小生成树具有很高的实际应用价值，比如要在若干城市之间建一个交通网，要求各个城市都能到达且造价最低，这就是一个典型的最小生成树问题。 一、普利姆算法（Prim）

1、设置一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态均为空集； 2、选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S1中； 3、重复下列操作，直到选取了n-1条边：

选取一条权值最小的边（X，Y），其中X∈S1， not(Y∈S1)； 将顶点Y加入集合 S1，边（X，Y）加入集合TE； 4、得到最小生成树T=（S1，TE）

下图给出了上图（A）的最小代价生成树的生成过程：

二、克鲁斯卡尔算法（Kruskal）

设最小生成树T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。

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

第五节 求图的最短路径算法

在带权图G=（V，E），若顶点Vi，Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。求最短路径具有很高的实用价值，在各种竞赛中经常遇到。一般有两类最短路径问题：一类是求从某个顶点（源点）到其他顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。

对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。 一、从一个顶点到其余各顶点的最短路径

如上图，假设C1，C2，C3，C4，C5，C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci的最短路径（2i≤6），输出路径序列及最短路径的路程长度。

对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路

径（1≤k≤n-2）。下面给出解决这个问题的Dijkstra算法思想。

设图G用邻接矩阵的方式存储在GA中，GA[I,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后没求出一个终点Vj，就把他加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。

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

二、任意一对顶点之间的最短路径

这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O(n)；另外还有一种算法：Floyed算法，他的思路简单，但时间复杂度仍然为O(n

3

3

)，下面介绍Floyed算法。

设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组A，A的初值等于GA。Floyed算法需要在A上进行n次运算，每次以Vk（1≤k≤n）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素A[I,j]就是图G中从顶点Vi到顶点Vj的最短路径长度。再设一个二维数组P[1..n,1..n]，记录最短路径。

第六节 拓扑排序算法

在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其他一些子工程（活动）完成之后才能开始，我们可以用有向图来形象的表示这些子工程

（活动）之间的先后关系，子工程为顶点，子工程之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。在AOV网中，有向边代表子工程的先后关系，即有向边的起点活动是终点活动的前驱活动，只有当起点活动完成之后终点活动才能进行。如果有一条从顶点Vi到Vj的路径，则说是Vi是Vj的前驱，Vj是Vi的后继。如果有弧，则称Vi是Vj的直接前驱，Vj是Vi的直接后继。

一个AOV网应该是一个有向无环图，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。

把不带回路的AOV网中的所有活动排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。需要注意的是AOV网的拓扑序列是不唯一的，如下图进行拓扑排序至少可以得到如下几种拓扑序列：02143567，01243657，02143657，01243567。

在上图所示的AOV网中，工程1和工程2显然可以同时进行，先后无所谓；但工程4却要等工程1和工程2都完成以后才可进行；工程3要等到工程l和工程4完成以后才可进行；工程5又要等到工程3、工程4完成以后才可进行；工程6则要等到工程4完成后才能进行；工程7要等到工程3、工程5、工程6都完成后才能进行。可见由AOV网构造拓扑序列具有很高的实际应用价值。

其实，构造拓扑序列的拓扑排序算法思想很简单：只要选择一个人度为0的顶点并输出，然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止，若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。 对上图进行拓扑排序的过程如下

(1)选择顶点0(惟一)， 输出0，删除边<0，1>,<0,2>； (2)选择顶点1(不惟—,可选顶点2)， 输出1，删除边<1,3>,<1,4>； (3)选择顶点2（唯一)， 输出2，删除边<2,4>；

(4)选择顶点4（唯一)， 输出4，删除边<4,3>,<4,5>,<4,6>；

(5)选择顶点3(不惟—，可选顶点6)， 输出3，删除边<3,5>,<3,7>； (6)选择顶点5(不惟—，可选顶点6)， 输出5，删除边<5,7>； (7)选择顶点6(惟一)， 输出6，删除边<6,7>； (8)选择顶点7(惟一)， 输出7，结束。

输出的顶点数m＝8，与AOV网中的顶点数n＝8相等，所以输出一种拓扑序列：01243567。 以下是将一AOV网进行拓扑排序的算法：

1、网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。

a、找到全为零的第 j 列，输出 j b、将第 j 行的全部元素置为零 c、找到全为零的第 k 列，输出 k d、将第 k 行的全部元素置为零 …………………

反复执行 c、d；直至所有元素输出完毕。 （1）计算各顶点的入度

（2）找入度为零的点输出之，删除该点，且与该点关联各点的入度减1 （3）若所有顶点都输出完毕。

2、以邻接表作存储结构（需在顶点表中增加一个记录顶点入度的域id） （1）把邻接表中所有入度为0的顶点进栈

（2）栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈

重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕

第七节 关键路径算法

利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利用带权的有向网。图中的边表示活动，边上的权表示完成该活动

所需要的时间，一条边的两个顶点分别表示活动的开始事件和结束事件，这种用边表示活动的网络，称为\网”。其中，有两个特殊的顶点(事件)，分别称为源点和汇点。源点表示整个工程的开始，通常令第一个事件(事件1)作为源点，它只有出边没有入边；汇点表示整个工程的结束，通常令最后一个事件(事件n)作为汇点，它只有入边没有出边；其余事件的编号为2到n—l。在实际应用中，AOE网应该是没有回路的，并且存在惟一的入度为0的源点和惟一的出度为0的汇点。

下图表示一个具有12个活动的AOE网。图中有8个顶点，分别表示事件0到7，其 中0表示开始事件，7表示结束事件，边上的权表示完成该活动所需要的时间。

AOE网络要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？

算法实现:

以邻接表作存储结构

从源点V1出发，令Ve[1]=0,按拓扑序列求各顶点的Ve[i]

从汇点Vn出发，令Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的Vl[i] 算法描述

输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序

– –

按逆拓扑序列求顶点的Vl[i]

计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动

排序过程中求顶点的Ve[i] 将得到的拓扑序列进栈

本文来源：https://www.bwwdw.com/article/cinr.html