文章目录
图的应用
本节是历年考查的重点。图的应用主要包括:最小生成(代价)树、最短路径、拓扑排序和关键路径。
一般而言，这部分内容直接以算法设计题形式考查的可能性极小，而更多的是结合图的实例来考查算法的具体操作过程，读者必须学会手工模拟给定图的各个算法的执行过程。
此外，还需掌握对给定模型建立相应的图去解决问题的方法。
考纲内容
（一）图的基本概念
（二）图的存储及基本操作
邻接矩阵；邻接表；邻接多重表；十字链表
（三）图的遍历
深度优先搜索；广度优先搜索
（四）图的基本应用
最小(代价)生成树；最短路径；拓扑排序；关键路径
复习提示
图算法的难度较大，主要掌握深度优先搜索与广度优先搜索。掌握图的基本概念及基本性质、图的存储结构(邻接矩阵、邻接表、邻接多重表和十字链表)及特性、存储结构之间的转化、基于存储结构上的各种遍历操作和各种应用(拓扑排序、最小生成树、最短路径和关键路径)等。
图的相关算法较多，通常只需掌握其基本思想和实现步骤，而实现代码不是重点。
1.最小生成树
一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。
对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；
若给它增加一条边，则会形成图中的一条回路。
对于一个带权连通无向图G，生成树不同，每棵树的权(即树中所有边上的权值之和)也可能不同。
权值之和最小的那棵生成树称为G的最小生成树(Minimum-Spanning-Tree,MST)。
【命题追踪——最小生成树的性质】
不难看出，最小生成树具有如下性质:
1) 若图G中存在权值相同的边，则G的最小生成树可能不唯一，即最小生成树的树形不唯一。
当图G中的各边权值互不相等时，G的最小生成树是唯一的；
若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。
2) 虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。
3) 最小生成树的边数为顶点数减 1。
【命题追踪——最小生成树中某顶点到其他顶点是否具有最短路径的分析】
注意：最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间的路径是最短路径。
如下图所示，最小生成树中A到C的路径长度为5，但原图中C到D的最短路径长度为4。
构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：
假设 G=(V，E)是一个带权连通无向图，U 是顶点集 V的一个非空子集。
若(u，v)是一条具有最小权值的边，其中 u∈U,v∈V-U，则必存在一棵包含边(u,v)的最小生成树。
基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略。
对这两种算法应主要掌握算法的本质含义和基本思想，并能够手工模拟算法的实现步骤。
下面介绍一个通用的最小生成树算法:
GENERIC MST(G){
T=NULL;
while T 未形成一棵生成树;
do 找到一条最小代价边(u,v)并且加入T后不会产生回路;
T=T∪(u,v);
}1.1Prim算法
Prim(普里姆)算法的执行非常类似于寻找图的最短路径的 Dijkstra算法(见下一节)。
【命题追踪——Prim 算法构造最小生成树的实例】
Prim 算法构造最小生成树的过程如图 6.15 所示。
初始时从图中任取一顶点(如顶点 1)加入树 T，此时树中只含有一个顶点，
之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。
以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。
此时T中必然有n-1条边。
Prim 算法的步骤如下:
假设 G={V,E)是连通图，其最小生成树，
是最小生成树中边的集合。
初始化：向空树中添加图 G=(V,E)的任意一个顶点
,使
，
。
循环(重复下列操作直至 U=V)：从图 G中选择满足{(u,v)|u∈U,v∈V-U,且具有最小权值的边(u,v)，加入树 T,置 U= U∪ {v},。
Prim 算法的简单实现如下:
void Prim(G,T){ //初始化空树
T=∅;
U={w}; //添加任意一个顶点w
while((V-U)!=∅){ //若树中不含全部顶点
设(u,v)是使u∈U与v∈(V-U),且权值最小的边;
T=T∪{(u,v)}; //边归入树
U=U∪{v}; //顶点归入树
}
}
Prim 算法的时间复杂度为 O(|V|²)，不依赖于|E|，因此它适用于求解边稠密的图的最小生成树。
虽然采用其他方法能改进 Prim 算法的时间复杂度，但增加了实现的复杂性。
1.2Kruskal算法
与 Prim 算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
【命题追踪——Kruskal 算法构造最小生成树的实例】
Kruskal 算法构造最小生成树的过程如图6.16所示。
初始时为只有n个顶点而无边的非连通图T={V，{}}，每个顶点自成一个连通分量。
然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，
若该边依附的顶点落在厂中不同的连通分量上(使用并查集判断这两个顶点是否属于同一棵集合树)，
则将此边加入T，否则舍弃此边而选择下一条权值最小的边。
以此类推，直至T中所有顶点都在一个连通分量上。
Kruskal 算法的步骤如下:
假设 G=(V,E)是连通图，其最小生成树 。
初始化：U=V，。即每个顶点构成一棵独立的树，T此时是一个仅含||V个顶点的森林。
循环(重复直至 T是一棵树)：按G的边的权值递增顺序依次从中选择一条边,
若这条边加入T后不构成回路，则将其加入，否则舍弃，直到
中含有n-1条边。
Kruskal 算法的简单实现如下:
void Kruskal(V,T){
T=V; //初始化树 T，仅含顶点
numS=n; //连通分量数
while(numS>1){ //若连通分量数大于1
从E中取出权值最小的边(v,u);
i£(v 和u属于T中不同的连通分量){
T=T∪{(v,u)}; //将此边加入生成树中
numS--; //连通分量数减1
}
}
}根据图的相关性质，若一条边连接了两棵不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树。
在 Kruskal 算法中，最坏情况需要对|E|条边各扫描一次。通常采用堆来存放边的集合，每次选择最小权值的边需要的时间；
每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 O(α(|V|))，α(|V|)的增长极其缓慢，可视为常数。
算法的总时间复杂度为，不依赖于|V|，因此 Kruskal 算法适合于边稀疏而顶点较多的图。