最小生成树
- 生成树（极小连通子图）：含有图中全部n个顶点，但只有n-1条边。并且n-1条边不能构成回路。
- 生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森林。
求最小生成树
- 使用不同的遍历图的方法，可以得到不同的生成树
- 从不同的顶点出发，也可能得到不同的生成树。
- 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
在网的多个生成树中，寻找一个各边 权值之和最小的生成树
构造最小生成树的准则
- 必须只使用该网中的边来构造最小生成树；
- 必须使用且仅使用n-1条边来联结网络中的n个顶点
- 不能使用产生回路的边
贪心算法(Greedy Algorithm)
- 算法原理：以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。
- 算法优点：因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效率高。
贪婪算法的精神就是“ 只顾如何获得眼前最大的利益”,有时不一定是最优解。
Prim（普里姆）算法
算法思想 —— 归并顶点
- 在图中任取一个顶点K作为开始点。令U={k}，W=V-U，其中V为图中所有顶点集
- 在U中选取一个顶点，W中选取另一个顶点，使二者对应的边是最短的一条。将该边作为最小生成树的边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点。
- 重新调整U中顶点到W中顶点的距离， 使之保持最小，再重复此过程，直到W为空集止。
算法设计
- 在算法中需要设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边
struct {
VertexType adjvex; // U集中的顶点
VRType lowcost; // 边的权值
} closedge[MAX_VERTEX_NUM];- lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
- adjvext[i]:表示对应lowcost[i]的起点，即说明边<adjvex[i],i>是MST的一条边，当adjvex[i]=0表示起点i加入MST
void MiniSpanTree_P(MGraph G, VertexType u){
// 用普利姆算法从顶点u出发构造网G的最小生成树
k = LocateVex_MG(G, u);
for(j = 0; j < G.vexnum; ++j) // 辅助数组初始化
if(j != k){
closedge[j].adjvex = new char[10];
strcpy(closedge[j].adjvex, G.vexs[k]);
closedge[j].lowcost = G.arcs[k][j].adj;
}
closedge[k].lowcost = 0; // 初始, U = {u}
closedge[k].adjvex = new char[10];
strcpy(closedge[k].adjvex, G.vexs[k]);
for(i = 0; i > G.vexnum; i ++){
// //继续向生成树上添加顶点
mincost = INF; // 找权值最小的顶点
for(m = 0; m < G.vexnum; ++m)
if(mincose > closedge[m].lowcost && closedge[m].lowcost != 0){
mincose = closedge[m].lowcost;
k = m;
} // 求出加入生成树的下一个顶点(k)
if(closedge[k].lowcost != 0)
//输出生成树上一条边
cout << closedge[k].adjvex << G.vexs[k] << closedge[k].lowcost;
closedge[k].lowcost = 0; // 第k顶点并入U集
for(j = 0; j < G.vexnum; j++)
// 修改其它顶点的最小边
if(G.arcs[k][j].adj < closedge[j].lowcost){
strcpy(closedge[j].adjvex, G.vexs[k]);
closedge[j].lowcost = G.arcs[k][j].adj;
}
}
}KrusKal（克鲁斯卡尔）算法
算法思想 —— 归并边
- 将图中所有边按权值递增顺序排列；
- 依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。
算法设计
构造非连通图 ST=( V,{ } );
k = i = 0; // k 计选中的边数
while (k<n-1) {
++i;
检查边集 E 中第 i 条权值最小的边(u,v);
**若(u,v)加入ST后不使ST中产生回路，
则 输出边(u,v); 且 k++;**
}
typedef struct {
// 增加边结构定义
int beginvex, endvex; // 边的起点、终点
VRType cost; // 边的权值
} edgetype;
edgetype edges[MAX_VERTEX_NUM];
void MiniSpanTree_Kruskal(ALGraph &G){
int parents[MAX_VERTEX_NUM];
cin >> G.vexnum >> G.arcnum; // 顶点数、弧数
for(i = 0; i < G.vexnum; i++){
// 建立顶点表
G.vertices[i].data = new char[10];
cin >> G.vertices[i].data; // 读入顶点信息并初始化
G.vertices[i].firstarc = NULL;
}
for(k = 0; k < G.arcnum; k++){
// 建立边表
v1 = new char[10];
v2 = new char[10];
cin >> v1 >> v2 >> w;
i = LocateVex_ALG(G, v1);
j = LocateVex_ALG(G, v2);
edges[k].beginvex = i;
edges[k].endvex = j;
edges[k].cost = w;
p = new ArcNode;
p->info = NULL;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
}
Sort(G, edges); // 按权值大小，对边进行排序
for(i = 0; i < G.vexnum; i++)
parents[i] = 0;
for(i = 0; i < G.arcnum; i++){
bnf = Find(parents, edges[i].beginvex); // 查找边头分量
edf = Find(parents, edges[i].endvex); // 查找边尾分量
if(bnf != edf){
parents[bnf] = edf;
cout << edges[i].beginvex << edges[i].endvex;
cout << " " << edges[i].cost << endl;
}
}
}
int Find(int parents[], int f){
// 查找函数
while(parents[f] > 0) f = parents[f];
return f;
}Prim和KrusKal比较
算法名 | Prim | KrusKal
时间复杂度 | O(n^2) | O(eloge)
适应范围 | 稠密图 | 稀疏图
