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

资源描述

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

《图论中的概念及重要算法.docx》由会员分享，可在线阅读，更多相关《图论中的概念及重要算法.docx（26页珍藏版）》请在冰点文库上搜索。

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

图论中的概念及重要算法

常州一中林厚从

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，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，v

2的入度是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，1≤j≤m；若此图是有向图，则∈E，1≤j≤m。

路径长度是指路径上的边或弧的数目。

序列中顶点不重复出现的路径称为简单路径，顶点v和顶点v’相同的路径称为回路（或环）。

除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路（或简单环）。

九、连通图

在无向图G中，如果从顶点U到顶点V有路径，则称U和V是连通的。

如果对于图G中的任意两个顶点U和V都是连通的，则称图G是连通图，否则称为非连通图。

在有向图G中，如果对于任意两个顶点U和V，从U到V和从V到U都存在路径，则称图G是强连通图。

Ch2、图的存储结构

一、邻接矩阵表示法

邻接矩阵是表示顶点之间相邻关系的矩阵，设G={V，E}是一个度为n的图（顶点序号分别用1，2，……，n表示），则G的邻接矩阵是一个n阶方阵，G[i,j]的值定义如下：

1或权值当vi与vj之间有边或弧时，取值为1或权值

G[i，j]=

0或∝当vi与vj之间无边或弧时，取值为0或∝（无穷大）

上面3个图对应的邻接矩阵分别如下：

0111011∞58∞3

G（A）=1011G（B）=001G（C）=5∞2∞6

110001082∞104

1100∞∞10∞11

36411∞

采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边（或弧），以及边上的权值，只要看A[

i,j]的值即可，因为可以根据i,j的值随机查找存取，所以时间复杂性为O

（1）。

也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性均为O（n）。

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

二、边集数组表示法

边集数组是利用一维数组存储图中所有边的一种图的表示方法。

每个数组元素存储一条边的起点、终点和权值（如果有的话）。

在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e），e为边数。

这种表示方法适合那些对边依次进行处理的运算，而不适合对顶点的运算和对任意一条边的运算。

从空间复杂性上讲，边集数组适合于存储稀疏图。

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

邻接表表示法是指对图中的每个顶点vi（1≤i≤n）建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。

为每个顶点vi（1≤i≤n）建立的单链表，是表示以该顶点为起点的所有边的信息（包括一个终点（邻接点）序号、一个权值和一个链接域）。

一维向量数组除了存储每个顶点的表头指针外，还要存储该顶点的编号i。

图（C）的邻接表表示为：

图的邻接表表示法便于查找任一顶点的关联边及邻接点，只要从表头向量中取出对应的表头指针，然后进行查找即可。

由于无向图的每个顶点的单链表平均长度为2e/n，所以查找运算的时间复杂性为O（e/n）。

对于有向图来说，想要查找一个顶点的后继顶点和以该顶点为起点的边、包括求该顶点的出度都很容易；但要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O（n+e）。

所以，对于经常查找顶点入度或以该顶点为终点的关联边的运算时，可以建立一个逆邻接表，该表中每个顶点的单链表存储的是所有以该点为终点的关联边信息。

甚至还可以把邻接表和逆邻接表结合起来，构造出“十字邻接表”，此时，每个边结点的数据信息包含五个域：

起点、终点、权、以该顶点为终点的关联边的链接、以该顶点为起点的关联边的链接。

表头向量的结点也包括三个域：

顶点编号、以该点为终点的表头指针域、以该点为起点的表头指针域。

Ch3、图的遍历

一、概念

从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。

为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。

图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。

后面的函授将专门讲解。

这儿我们先作个介绍。

二、深度优先遍历

从图中某个顶点Vi出发，访问此顶点并作已访问标记，然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历，当Vi的所有邻接点都被访问过时，则退回到上一个顶点Vk，再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。

如下面的左图从顶点a出发，进行深度优先遍历的结果为：

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，V5，V6，V7，V8。

两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存（用队列，先进先出），以便进一步进行广度优先遍历。

ch4、图的重要算法

一、求图的最小生成树算法

如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V，E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。

同一个图可以有不同的生成树，但可以证明：

n个顶点的连通图的生成树必定含有n-1条边。

对于加权连通图（连通网），生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。

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

那么如何求（最小）生成树呢？

求（最小）生成树可以从某个顶点采用深度优先遍历的方法，也可采用广度优先遍历的方法，分别称为深度优先生成树和广度优先生成树。

上图中的图（B）和图（C）所示两棵生成树，是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树。

也可以综合应用深度优先遍历和广度优先遍历的特定算法，如：

Prim算法和Kruskal算法，下面我们将分别介绍。

1、用Prim算法求最小生成树的思想如下：

（设图G的度为n，G=（V，E））

①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；

②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；

③重复下列操作，直到选取了n-1条边：

选取一条权值最小的边（X，Y），其中X∈S，not（Y∈S）；

将顶点Y加入集合S，边（X，Y）加入集合TE；

④得到最小生成树T=（S，TE）

下面给出Prim算法构造图的最小生成树的具体算法框架。

①从文件中读入图的邻接矩阵g；

②边集数组elist初始化；

Fori:

=1Ton-1Do

Begin

elist[i].fromv:

=1；elist[i].endv:

=i+1；elist[i].weight:

=g[1,i+1]；

End；

③求出最小生成树的n-1条边；

Fork:

=1Ton-1Do

Begin

min:

=maxint；m:

=k；

Forj:

=kTon-1Do{查找权值最小的一条边}

Ifelist[j].weight

=elist[j].weight；m:

=j；End；

Ifm<>kThenBegint:

=elist[k]；elist[k]:

=elist[m]；elist[m]:

=t；End；

{把权值最小的边调到第k个单元}

=elist[k].endv；{j为新加入的顶点}

Fori:

=k+1Ton-1Do{修改未加入的边集}

Begins:

=elist[i].endv；w:

=g[j,s]；

Ifw

ThenBeginelist[i].weight:

=w；elist[i].fromv:

=j；End；

End；

④输出；

2、用Kruskal算法求最小生成树的思想如下：

（设图G的度为n，G=（V，E））

设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。

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

最后的T即为最小生成树。

Kruskal算法在实现过程中的关键和难点在于：

如何判断欲加入的一条边是否与生成树中已保留的边形成回路？

我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。

当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。

如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。

下面给出利用Kruskal算法构造图的最小生成树的具体算法框架。

1将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序；

2设数组C[1..n-1]用来存储最小生成树的所有边，C[i]是第i次选取的可行边在排好序的elist中的下标；

③设一个数组S[1..n]，S[i]都是集合，初始时S[i]=[i]。

3i:

=1；{获取的第i条最小生成树的边}

=1；{边集数组的下标}

Whilei<=n-1Do

Begin

Fork:

=1TonDoBegin{取出第j条边，记下两个顶点分属的集合序号}

Ifelist[j].fromvins[k]Thenm1:

=k；

Ifelist[j].endvins[k]Thenm2:

=k；

End；

Ifm1<>m2ThenBegin{找到的elist第j条边满足条件，作为第i条边保留}

C[i]:

=j；

=i+1；

s[m1]:

=s[m1]+s[m2]；{合并两个集合}

s[m2]:

=[]；{另一集合置空}

End；

=j+1；{取下条边，继续判断}

End；

4输出最小生成树的各边：

elist[C[i]]

二、求图的最短路径算法

在带权图G=（V，E）中，若顶点Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。

从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。

求最短路径具有很高的实用价值，在各种竞赛中经常遇到。

一般有两类最短路径问题：

一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。

对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。

1、从一个顶点到其余各顶点的最短路径

看上图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。

请编写一程序，找出C1到Ci的最短路径（2≤i≤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数组中保存着相应的最段路径。

对于上图，采用Dijkstra算法找出C1到Ci之间的最短路径（2≤i≤6）的过程如下：

初始时：

Dist

maxint

Path

C1,C2

C1,C3

第一次：

选择m=2，则S=[C1,C2]，计算比较dist[2]+GA[2,j]与dist[j]的大小（3≤j≤6）

Dist

maxint

Path

C1,C2

C1,C2,C3

C1,C2,C4

C1,C2,C5

第二次：

选择m=3，则S=[C1,C2,C3]，计算比较dist[3]+GA[3,j]与dist[j]的大小（4≤j≤6）

Dist

maxint

Path

C1,C2

C1,C2,C3

C1,C2,C4

C1,C2,C3,C5

第三次：

选择m=4，S=[C1,C2,C3,C4]，计算比较dist[4]+GA[4,j]与dist[j]的大小（5≤j≤6）

Dist

Path

C1,C2

C1,C2,C3

C1,C2,C4

C1,C2,C3,C5

C1,C2,C4,C6

第四次：

选择m=5，则S=[C1,C2,C3,C4,C5]，计算比较dist[5]+GA[5,j]与dist[j]的大小（j=6）

Dist

Path

C1,C2

C1,C2,C3

C1,C2,C4

C1,C2,C3,C5

C1,C2,C3,C5,C6

因为该图的度n=6，所以执行n-2=4次后结束，此时通过dist和path数组可以看出：

C1到C2的最短路径为：

C1——C2，长度为：

4；

C1到C3的最短路径为：

C1——C2——C3，长度为：

7；

C1到C4的最短路径为：

C1——C2——C4，长度为：

8；

C1到C5的最短路径为：

C1——C2——C3——C5，长度为：

9；

C1到C6的最短路径为：

C1——C2——C3——C5——C6，长度为：

13；

下面给出具体的Dijkstra算法框架（注：

为了实现上的方便，我们用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。

ProcedureDijkstra（GA,dist,path,i）；{表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合}

Begin

Forj:

=1TonDoBegin{初始化}

Ifj<>iThens[j]:

Elses[j]:

=1；

dist[j]:

=GA[i,j]；

Ifdist[j]

Thenpath[j]:

=[i]+[j]

Elsepath[j]:

=[]；

End；

Fork:

=1Ton-2Do

Begin

=maxint；m:

=i；

Forj:

=1TonDo{求出第k个终点Vm}

If（s[j]=0）and（dist[j]

=j；w:

=dist[j]；End；

Ifm<>iThens[m]:

=1elseexit；{若条件成立，则把Vm加入到S中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去}

Forj:

=1TonDo{对s[j]=0的更优元素作必要修改}

If（s[j]=0）and（dist[m]+GA[m,j]

ThenBegin

Dist[j]:

=dist[m]+GA[m,j]；

path[j]:

=path[m]+[j]；

End；

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

这个问题的解法有两种：

一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：

Floyed算法，它的思路简单，但时间复杂度仍然为O（n

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]，记录最短路径，其元素类型为集合类型setof1..n。

Floyed算法的具体描述如下：

ProcedureFloyed（GA，A，P）；

Begin

Fori:

=1TonDo{最短路径长度数组和最短路径数组初始化}

Forj:

=1TonDo

Begin

A[i,j]:

=GA[i,j]；

IfA[i,j]

=[i]+[j]

Elsep[i,j]:

=[]；

End；

Fork:

=1TonDo{n次运算}

Fori:

=1TonDo

Forj:

=1TonDo

Begin

If（i=k）or（j=k）or（i=j）ThenContinue；

{无需计算，直接进入下一轮循环}

IfA[i,k]+A[k,j]

A[i,j]：

=A[i,k]+A[k,j]；

P[i,j]：

=P[i,k]+P[k,j]；

End；

对于上图，大家可以运用Floyed算法，手工或编程找出任意一对顶点之间的最短路径及其长度。

三、拓扑排序算法

在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先

展开阅读全文