最小生成树
2022-09-02 本文已影响0人
lxr_
生成树：
- 所有顶点均由边连接在一起，但不存在回路的图。
- 一个有n个顶点的连通图的生成树具有n-1条边；
- 一个图可以有许多棵不同的生成树；
- 生成树的顶点个数与图的顶点个数相同；
- 生成树是图的极小连通子图，去掉一条边则非连通；
- 生成树任意两个顶点间的路径是唯一的；
- 含有n个顶点n-1条边的图不一定是生成树。
无向图的生成树：
- 设图G=(V,E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分成两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边和集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图的极小连通子图，即子图G1是连通图G的生成树。由于遍历算法的不同可分为深度优先生成树和广度优先生成树。
最小生成树：
- 给定一个无向网图，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树（Minimum Cost Spanning Tree）。
- 构造最小生成树的算法有很多，多数都利用了MST的性质，即：
设N=V(V,E)是一个连通网，U是顶点集V的一个非空子集。若边(u,v)是一条具有最小权值的边，其中u属于U，v属于V-U,则必然存在一棵包含边(u,v)的最小生成树。
性质解释： - 图中n个顶点分为两个集合：
（1）已落在生成树上的顶点集：U
（2）尚未落在生成树上的顶点集：V-U
（3）接下来应该在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
普里姆算法（Prim）算法：
（1）设N=(V,E)是连通网，TE是N上最小生成树中边的集合；
（2）初始令U={u0}，(u0属于V)，TE={}；
（3）在所有u属于U，v属于V-U的边（u,v）属于E中，找一条代价最小的边(u0,v0)；
（4）将(u0,v0)并入集合TE，同时v0并入U；
（5）重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树
克鲁斯卡尔（Kruskal）算法：
（1）设连通网N=(V,E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{}),每个顶点自成一个连通分量。
（2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。
（3）依次类推，直至T中所有顶点都在同一连通分量上为止。
两种算法对比：
算法对比
代码示例
关于图的邻接矩阵结构创建可查看以前的文章https://www.jianshu.com/p/b50ba1b3c327
MGraph.h
//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G);
//克鲁斯卡尔算法
struct Edge //定义边集数组结构
{
int begin; //边的起点
int end; //边的终点
int weight; //边的权重
Edge operator=(const Edge& e)
{
begin = e.begin;
end = e.end;
weight = e.weight;
return *this;
}
};
//将邻接矩阵转换为边集数组并按照权值升序排序
void MGraph2Edge(MGraph G, Edge edges[]);
//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G);
//查找连线顶点的尾部下标
int Find(int* parent, int f);
MGraph.cpp
//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
//step1:初始化
int adjvex[MAXVEX]; //保存最小生成树中边的一端顶点（其实是已在生成树中的顶点）
int lowcost[MAXVEX]; //保存相关顶点间边的权值
lowcost[0] = 0; //初始化第一个权值为0，即v0加入生成树，通过此数组记录已加入生成树的顶点与其它顶点之间的边的最小值
adjvex[0] = 0; //初始化第一个顶点下标为0，通过此数组记录已加入生成树的顶点
for (int i = 1; i < G.numVertexes; i++) //遍历除了v0顶点的其它顶点
{
lowcost[i] = G.arc[0][i]; //记录顶点v0与其它边的权值
adjvex[i] = 0; //顶点v0
} //初始化完成
//step2:寻找下一个加入生成树的顶点
int k;
for (int i = 1; i < G.numVertexes; i++) //遍历每个顶点
{
int min = MAXEDGE; //初始化最小权值为无穷大
for (int j = 1; j < G.numVertexes; j++) //遍历lowcost寻找最小权值
{
if (lowcost[j] && lowcost[j] < min) //如果该顶点还未加入生成树
{
min = lowcost[j];
k = j; //找到最小权值边对应的顶点
}
}
cout << "(" << adjvex[k] << "," //输出最小权值的边
<< k << ")" <<
"(" << G.vexs[adjvex[k]] << "," //输出最小权值的边
<< G.vexs[k] << ")" << endl;
//step3:更新已加入生成树的顶点与其它顶点之间的最小值
for (int m = 1; m < G.numVertexes; m++)
{
if (lowcost[m] && G.arc[k][m] < lowcost[m]) //新加入的顶点与其它顶点之间的边的最小值是否足够小
{
lowcost[m] = G.arc[k][m];
adjvex[m] = k; //新加入的顶点k与m之间的边为候选
}
}
}
}
//克鲁斯卡尔算法
//将邻接矩阵转换为边集数组并按照权值升序排序
void MGraph2Edge(MGraph MG, Edge edges[])
{
int k = 0; //记录插入个数
for (int i = 0; i < MG.numVertexes; i++)
{
for (int j = 0; j < i; j++)
{
int weight = MG.arc[i][j];
if (weight > 0 && weight < MAXEDGE)
{
Edge edge;
edge.begin = i;
edge.end = j;
edge.weight = weight;
if (k == 0) //第一个直接插入
{
edges[k] = edge;
}
else
{
int n = k - 1; //最后一个元素的位置
if (weight < edges[n].weight) //如果待插入元素小于已经排好序的有序数组中最后一个元素
{
for (; weight < edges[n].weight; n--)
{
edges[n + 1] = edges[n];
}
}
edges[n + 1] = edge; //插入
}
k++;
}
}
}
}
//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
{
Edge edges[MAXEDGE] = { 0 }; //边集数组
int parent[MAXVEX] ; //用于判断是否形成环
for (int i = 0; i < G.numVertexes; i++)
{
parent[i] = -1;
}
MGraph2Edge(G, edges); //计算边集数组并按照权值升序排序
for (int i = 0; i < G.numEdges; i++) //遍历每一条边
{
int n = Find(parent, edges[i].begin); //寻找此边的顶点begin是否在生成树中
int m = Find(parent, edges[i].end); //寻找此边的顶点end是否在生成树中
if (n != m) //不相等说明此边没有与现有生成树形成环路，两个顶点在不同的连通分量上
{
parent[n] = m; //将此边的结尾顶点放入下标为起点的parent中，表示顶点n,m已经在生成树集合中，
cout << "(" << edges[i].begin << "," << edges[i].end << ") " << edges[i].weight << endl;
}
}
}
//查找连线顶点的尾部下标，判断顶点f是否已经连接到生成树中
int Find(int* parent, int f)
{
while (parent[f] > -1)
{
f = parent[f];
}
return f;
}
main.cpp
#include <iostream>
#include "MGraph.h"
#include "ALGraph.h"
using namespace std;
extern bool* visited, * visited1;
int main(int argc, char** argv)
{
//1.邻接矩阵
MGraph MG;
CreateMGrah(MG);
for (int i = 0; i < MG.numVertexes; i++) //对于连通图，只执行一次
{
if (!visited[i])
{
DFS(MG, i); //深度优先搜索遍历
//BFS(MG, 0); //广度优先搜索遍历
}
}
cout << "\nPrim 最小生成树：" << endl;
/*
A D 1
A E 3
A B 7
B C 5
B E 2
C D 6
C E 8
D E 4
*/
MiniSpanTree_Prim(MG);
cout << "\nKruskal 最小生成树：" << endl;
//Edge edges[MAXEDGE] = { 0 };
//MGraph2Edge(MG, edges);
MiniSpanTree_Kruskal(MG);
return 0;
}
