2021年度图专题教育课件讲义.ppt

1、最小生成树的定义：如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。
2、MST性质：设G=(V,E)是带权的连通图，U是顶点V的非空子集。(u,v)是一条具有最小权值的边，u属于U,v属于V-U,则必存在一棵包含该边的最小生成树。
最小生成树
2021/1/31
1
图专题教育课件
3、prim算法：
Prim算法的基本思想：
⑴ 若从顶点v0出发构造，U={v0}，TE={}；
⑵ 先找权值最小的边(u，v)，其中u∈U且v∈V-U，并且子图不构成环，则U= U∪{v}，TE=TE∪{(u，v)} ；
⑶ 重复⑵ ，直到U=V为止。则TE中必有n-1条边， T=(U，TE)就是最小生成树。
v1
v3
v2
v4
v5
4
8
5
7
12
11
3
6
2021/1/31
2
图专题教育课件
存储结构的定义：
设用邻接矩阵表示图。为便于算法实现，设置一个一维数组lowcost[n]，用来保存V- U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是：
struct
{
int adjvex ; /* 边所依附于U中的顶点 */
int cost ; /* 该边的权值 */
} lowcost[MAX_EDGE] ;
lowcost[j].adjvex=k，表明边(vj, vk)是V-U中顶点vj到U中权值最小的边，而顶点vk是该边所依附的U中的顶点。 lowcost[j]. cost存放该边的权值。
2021/1/31
3
图专题教育课件
算法步骤：
（1）初始化：假设从顶点vs开始构造最小生成树:
表示V-U中的各顶点到U中权值最小的边(k≠s) ，cost(k, s)表示边(vk, vs) 权值。
lowcost[s]. cost=0 ：表明顶点vs首先加入到U中；
lowcost[k].adjvex=s ，lowcost[k].cost=cost(k, s)
2021/1/31
4
图专题教育课件
（2）从lowcost中选择一条权值(不为0)最小的边(vk, vi) ，然后做：
置lowcost[k].lowcost为0 ，表示vk已加入到U中。
根据新加入vk的更新lowcost中每个元素：若cost(i,k)≦lowcost[i].cost，表明在U中新加入顶点vk后,(vi, vk)成为vi到U中权值最小的边，置：
（3）重复（2）n-1次就得到最小生成树。
lowcost[i].cost=cost(i, k)
lowcost[i].adjvex=k
2021/1/31
5
图专题教育课件
算法程序:
算法分析:
设带权连通图有n个顶点，，整个算法的时间复杂度是O(n2)，与边的数目无关。
2021/1/31
6
图专题教育课件
4、克鲁斯卡尔(Kruskal)算法：
Kruskal算法的基本思想：设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是其最小生成树。初值：U=V，TE={} 。对G中的边按权值大小从小到大依次选取。
⑴ 选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边(边(vi，vj) ；否则，将该边并入到TE中，即TE=TE∪{(vivj)} 。
⑵ 重复⑴ ，直到TE中包含有n-1条边为止。
v1
v3
v2
v4
v5
4
8
5
7
12
11
3
6
2021/1/31
7
图专题教育课件
Kruskal算法实现的关键是：当一条边加入到TE的集合后，如何判断是否构成回路?
简单的解决方法是：定义一个一维数组Vset[n] ，存放图T中每个顶点所在的连通分量的编号。
初值：Vset[i]=i，表示每个顶点各自组成一个连通分量，连通分量的编号简单地使用顶点在图中的位置(编号)。
当往T中增加一条边(vi，vj) 时，先检查Vset[i]和Vset[j]值：
（1）若Vset[i]=Vset[j]：表明vi和vj处在同一个连通分量中，加入此边会形成回路；
（2）若Vset[i]≠Vset[j]，则加入此边不会形成回路，将此边加入到生成树的边集中。加入一条新边后，将两个不同的连通分量合并：将一个连通分量的编号换成另一个连通分量的编号。
2021/1/31
8
图专题教育课件
算法步骤：使用一个小根堆和并查集,先用小根堆存储图中