【贪心算法】最小生成树(Prim算法 & Kruskal算法)(C++)
一、最小生成树问题1. 问题描述设G =(V,E)是无向连通带权图,即一个网络。(V是顶点集合,E是边集合)如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。2. 算法分析Prim算法和Kruskal算法:都是解最小生成树问题的贪心算法;它们做贪心选择的方式不同,但都利用了下面的最小生成
一、最小生成树问题
1. 问题描述
- 设G =(V,E)是无向连通带权图,即一个网络。(V是顶点集合,E是边集合)
- 如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。
- 在G的所有生成树中,耗费最小的生成树称为G的最小生成树。
2. 算法分析
- Prim算法和Kruskal算法:都是解最小生成树问题的贪心算法;它们做贪心选择的方式不同,但都利用了下面的最小生成树性质。
最小生成树性质:
- 设G=(V,E)是连通带权图,U是V的真子集。
- 如果(i,j)∈E,且i∈U,j∈V-U,且在所有这样的边中,(i,j)的权c[i][j]最小,那么必存在一棵包含边(i,j)的最小生成树。
- 这个性质也称为MST(Minimum Spanning Tree)性质。
2.1. Prim算法
-
贪心选择策略: 每次都选择到下一顶点权最小的边。
-
基本步骤:
- 置顶点集合S={1};
- 只要S是V的真子集,就作如下的贪心选择:选取满足条件i∈S,j∈V-S,且c[i][j]最小的边,将顶点j添加到S中。
- 这个过程一直进行到S=V时为止,选取到的所有边恰好构成G的一棵最小生成树。
-
举个例子: 对于图1中的连通带权图,按Prim算法选取边的过程如图2。
2.2. Kruskal算法
-
贪心选择策略: 每次都选择权最小的可以连通两个不同连通分支的边。
-
基本步骤:
- 将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。
- 从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接2个不同的连通分支:
- 当查看到第k条边(v,w)时,如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时,就用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边;
- 如果端点v和w在当前的同一个连通分支中,就直接再查看第k+1条边;
- 这个过程一直进行到只剩下一个连通分支时为止,选取到的所有边恰好构成G的一棵最小生成树。
-
举个例子: 对于图1中的连通带权图,按Kruskal算法选取边的过程如图3。
[注]:无向连通带权图 --> 邻接矩阵
-
用一个二维数组存放顶点间关系(边或弧)的数据,这个二维数组称为邻接矩阵;
-
每条带权无向边(v,w)的权存入矩阵c[v][w];矩阵其余项为∞。
-
以图1为例:
邻 接 矩 阵 A = [ ∞ 6 1 5 ∞ ∞ 6 ∞ 5 ∞ 3 ∞ 1 5 ∞ 5 6 4 5 ∞ 5 ∞ ∞ 2 ∞ 3 6 ∞ ∞ 6 ∞ ∞ 4 2 6 ∞ ] 邻接矩阵 A=\begin{bmatrix} \infty & 6 & 1 & 5 & \infty & \infty \\ 6 & \infty & 5 & \infty & 3 & \infty \\ 1 & 5 & \infty & 5 & 6 & 4 \\ 5 & \infty & 5 & \infty & \infty & 2 \\ \infty & 3 & 6 & \infty & \infty & 6 \\ \infty & \infty & 4 & 2 & 6 & \infty \\ \end{bmatrix} 邻接矩阵A=⎣⎢⎢⎢⎢⎢⎢⎡∞615∞∞6∞5∞3∞15∞5645∞5∞∞2∞36∞∞6∞∞426∞⎦⎥⎥⎥⎥⎥⎥⎤
二、算法实现
1. Prim算法
// 【贪心算法】最小生成树问题 - Prim算法
#include <iostream>
using namespace std;
#define M 9999 // maxint,inf,大数
const int N = 6;// 无向连通带权图的 顶点数
void Prim(int n, int c[][N + 1]);
int main()
{
// 无向连通带权图的邻接矩阵,行和列下标从1开始
int c[N + 1][N + 1] = {
{M, M, M, M, M, M, M},
{M, M, 6, 1, 5, M, M},
{M, 6, M, 5, M, 3, M},
{M, 1, 5, M, 5, 6, 4},
{M, 5, M, 5, M, M, 2},
{M, M, 3, 6, M, M, 6},
{M, M, M, 4, 2, 6, M},
};
cout << "无向连通带权图的矩阵为:\n";
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
cout << c[i][j] << "\t";
cout << endl;
}
cout << "\nPrim算法最小生成树选边次序:" << endl;
Prim(N, c);
return 0;
}
void Prim(int n, int c[][N + 1])
{
// 顶点j属于V-S,closest[j]是顶点j在S中的 最邻接顶点
int closest[N + 1]; // j的 最邻接顶点
// 顶点j属于V-S,顶点j到closest[j]和S中的其它邻接顶点k相比
// c[j][closest[j]] <= c[j][k],即最小权值
int lowcost[N + 1]; // 最小权值,c[j][closest[j]]
bool s[N + 1]; // 顶点集合S
s[1] = true; // 初始S={1}
//初始化
for (int i = 2; i <= n; i++)
{
closest[i] = 1;
lowcost[i] = c[1][i];
s[i] = false;
}
for (int i = 1; i < n; i++)
{
int min = M;
int j = 1;
// 找出V-S中使权值最小的顶点j
for (int k = 2; k <= n; k++)
{
if ((lowcost[k] < min) && (!s[k]))
{
min = lowcost[k];
j = k;
}
}
// 找到符合贪心选择方式的边,将顶点j加入到集合S
cout << closest[j] << "--" << j << endl;
s[j] = true;
// 找到一条边后,更新数组closest和lowcost
for (int k = 2; k <= n; k++)
{
if ((c[j][k] < lowcost[k] && (!s[k])))
{
lowcost[k] = c[j][k];
closest[k] = j;
}
}
}
}
2. Kruskal算法(这是书上的,待续…)
// 【贪心算法】最小生成树问题 - Kruskal算法
template <class Type>
class EdgeNode
{
friend ostream& operator <<(ostream&, EdgeNode<Type>);
friend bool Kruskal(int, int, EdgeNode<Type>*, EdgeNode<Type>*);
friend int main(void);
public:
operator Type() const
{
return weight;
}
private:
Type weight;
int u, v;
};
template <class Type>
bool Kruskal(int n, int e, EdgeNode<Type> E[], EdgeNode<Type> t[])
{
MinHeap<EdgeNode<Type>> H(1);
H.Initialize(E, e, e);
UnionFind U(n);
int k = 0;
while (e && k < n - 1)
{
EdgeNode<int> x;
H.DeleteMin(x);
e--;
int a = U.Find(x.u);
int b = U.Find(x.v);
if (a != b)
{
t[k++] = x;
U.Union(a, b);
}
}
H.Deactivate();
return (k == n - 1);
}
3. 运行结果展示
三、友情链接~
- 其它一些常见算法请参阅此链接~
最后,非常欢迎大家来讨论指正哦!
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)