文档介绍：图论算法
图论在信息学竞赛中占了很大部分,很多实际问题可以用图论来解决。
江苏省金湖中学张厚林
图的一些典型算法
最小生成树
最短路径
拓扑排序
关键路径
例1、最优工程造价
[描述]有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少。

这是我们想要的结果
★这类问题,可归纳为图的最小生成树问题

一个图的生成树具备三个条件:
(1)顶点是图的全部顶点;
(2)边是图的部分边,且将图中所有顶点连通
(3)不构成回路
由此可以看出,一个图的生成树是不唯一的
可以证明:具有n个顶点的带权连通图,其对应的生成树有条边。
n-1

权值最小的生成树,称为图的最小生成树。
下图(B)、(C)、(D)均是图(A)的生成树,其权和分别为20、33和19,前两个并不是最小生成树,只有图(D)是最小生成树。
具有n个顶点的带权连通图,其对应的生成树有n-1条边! 那么到底选哪n-1条边呢?
请思考:

核心:选取哪n-1条边
方法一:基于搜索的两种算法
深度优先遍历
广度优先遍历
深度优先遍历
广度优先遍历
结论:若要使权值总和最小,必须所有情况均需搜索,当顶点数和边数较大时,复杂度很高。
同学们,你们有没有更好的方法?
练一练:写出上图用Kruskal算法实现最小生成树的过程?
思考:如何判断欲加入的一条边是否与生成树中已保留的边形成回路?
Kruskal算法
①设最小生成树为T=(V,TE),设置边的集合TE的初始状态为[1] [2] [3] [4] [5] ……[n],将图G中的边按权值从小到大排好序。
②找权值最小的边(i,j),且i、j不属同一集合。
③将i、j所在集合合并。
重复n-1次②~③。最后的T即为最小生成树。
i:=1;{获取的第i条最小生成树的边}
j:=1;{边集数组的下标}
While i<=n-1 Do Begin
For k:=1 To n Do Begin
{取出第j条边,记下两个顶点分属的集合序号}
End;
If m1<>m2 Then Begin
{找到的elist第j条边满足条件,作为第i条边保留}
End;
j:=j+1; {取下条边,继续判断}
End;
④输出最小生成树的各边:elist[C[i]]
C[i]:=j;i:=i+1;
s[m1]:=s[m1]+s[m2];{合并两个集合}
s[m2]:=[ ]; {另一集合置空}
If elist[j].fromv in s[k] Then m1:=k;
If elist[j].endv in s[k] Then m2:=k;
练一练:写出上图用Prim算法实现最小生成树的过程?
Prim算法
①设置一个顶点的集合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算法
Kruskal算法