Prim算法如何绘制最小生成树图解？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1675个文字，预计阅读时间需要7分钟。
Prim算法+最小生成树+图解：什么是生成树+子图：G=V,E,C，G'=V',E',C'，为两个图（V为点集，E为边集），若V'=V，E'=E，则称G'为G的子图。若V'=V，E'是E的子集，则称G'为G的子图。若G'=G，则称G'为G的子图。
Prim 最小生成树 图解 什么是生成树
子图：G=<V，E>，G'=<V', E'>，为两个图（V为点集，即图中点的集合，E为边集），如果V'是V的子集且E'是E的子集，则G'是G的子图。
如果V'=V，则称G'为G的生成子图
如果G'是无向生成子图且是树的结构，则为生成树
最小生成树
最小生成树：是一张有权无向连通图中边权和最小的生成树
Prim算法：维护一个已经加入最小生成树的点的集合C，每次通过一条边连接一个不在这个点集C的点，直到最后形成一个树形结构
Dist(u)表示u点到点集C中的点的最小距离
每次选择一个到点集C距离最小的点加入点集C，并通过加入的点去更新未加入的点到点集C的最小距离（因为C中多加了一个点），直到n个点全部加入点集C或没有点能够加入（不能构成连通图）。
图解
前言：已经加入点集C的点标记为蓝色，当前加入的点标记为红色，被当前加入的点更新的dist标记为红色。
初始：加入一个初始点A，并通过A更新dist
u A B C D E F dist(u) 0 3 5 inf inf inf加入第二个点B：B到点集C距离最小，并通过B更新dist
u A B C D E F dist(u) 0 3 1 8 3 inf加入第三个点C：C到点集C距离最小，并通过C更新dist
u A B C D E F dist(u) 0 3 1 8 3 inf加入第四个点E：E到点集C距离最小，并通过E更新dist
u A B C D E F dist(u) 0 3 1 2 3 1加入第五个点F：F到点集C距离最小，并通过F更新dist
u A B C D E F dist(u) 0 3 1 2 3 1加入第六个点D：D到点集C距离最小，并通过D更新dist
u A B C D E F dist(u) 0 3 1 2 3 1点全部加入点集，Prim算法结束。
复杂度分析：
总共需要加入n个点，每次需要遍历dist数组找最小值，并通过该点更新未加入点集的dist值，即枚举该点连出的边更新对应的dist，故复杂度为：
O（n*n）+ = O（n*n + m）（mi为每个点连出的边的条数，总和为总边数）
伪代码：
模板题int prim()
{
memset(dis, 127, sizeof(dis)); //初始设置为正无穷
memset(vis, 0, sizeof(vis)); //初始设置点均不在点集中,点集为空
ans = 0, cnt = 0; //初始权值为0
dis[1] = 0; // 1加入点集
while (1)
{
int u = -1;
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0 && dis[i] < (1 << 30)) // i点不在点集中并且与点集中的点联通
{
if (u == -1 || dis[i] < dis[u]) // u==-1 ->第一个点可以更新到点集最近的点
{
u = i; //更新最近的点
}
}
}
if (u == -1)
break; //如果不能找到加入点集的点，则结束算法
cnt++, ans += dis[u]; //点集中点的个数+1，ans加上u连入点集的边权
vis[u] = true; // vis加入点集
for (auto it : a[u])//a[u]为以u连出的边的点的集合，v为相连的点，w为边权
{
dis[it.v] = min(dis[it.v], it.w); //通过点v连出的边更新不在点集的点的dist值
}
}
if (cnt == n)
return ans; //能够加入n个点构成连通图，生成树则返回权值
else
return -1; //不能形成生成树
}
题目链接：最小生成树1 - 题目 - Daimayuan Online Judge
题目描述：
给你一张简单无向连通图，边权都为非负整数。你需要求出它的最小生成树，只需要输出边的权值和即可。
图用以下形式给出：
第一行输入两个整数n,m，表示图的顶点数、边数，顶点编号从1到n。
接下来m行，每行三个整数x,y,z 表示x与y之间有一条边，边权为z。
输入格式：
第一行两个整数n,m。
接下来m行，每行有三个整数，代表一条边。
输出格式：
输出一个数，表示最小生成树的权值和。
数据规模：
对于所有数据，保证2≤n≤1000,n−1≤m≤100000,1≤x,y≤n,x≠y,1≤z≤10000
样例输入：
4 4
1 2 1
2 3 3
3 4 1
1 4 2
样例输出：
4
详见代码：
#include <bits/stdc++.h>
using namespace std;
int dis[100009], cnt, ans, n, m; // dis为点到点集的最小距离，cnt为点集中点的个数，ans为当前的边权和
bool vis[100009];
struct node
{
int v, w;
};
vector<node> a[100009]; //存图
int prim()
{
memset(dis, 127, sizeof(dis)); //初始设置为正无穷
memset(vis, 0, sizeof(vis)); //初始设置点均不在点集中,点集为空
ans = 0, cnt = 0; //初始权值为0
dis[1] = 0; // 1加入点集
while (1)
{
int u = -1;
for (int i = 1; i <= n; i++) //遍历找未加入点集的最小距离的点
{
if (vis[i] == 0 && dis[i] < (1 << 30)) // i点不在点集中并且与点集中的点联通
{
if (u == -1 || dis[i] < dis[u]) // u==-1 ->第一个点可以更新到点集最近的点
{
u = i; //更新最近的点
}
}
}
if (u == -1)
break; //如果不能找到加入点集的点，则结束算法
cnt++, ans += dis[u]; //点集中点的个数+1，ans加上u连入点集的边权
vis[u] = true; // vis加入点集
for (auto it : a[u])
{
dis[it.v] = min(dis[it.v], it.w); //通过点v连出的边更新不在点集的点的dist值
}
}
if (cnt == n)
return ans; //能够加入n个点构成连通图，生成树则返回权值
else
return -1; //不能形成生成树
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
node t1, t2; //无向图存边
t1.v = v, t1.w = w;
a[u].push_back(t1); // u->v 边权为w
t2.v = u, t2.w = w;
a[v].push_back(t2); // v->u 边权为w
}
cout << prim();
}
参考文献：
2022 Namomo Spring Camp Div2 Day10直播课
ending
有什么错误之处欢迎指正！不胜感激！
本文共计1675个文字，预计阅读时间需要7分钟。
Prim算法+最小生成树+图解：什么是生成树+子图：G=V,E,C，G'=V',E',C'，为两个图（V为点集，E为边集），若V'=V，E'=E，则称G'为G的子图。若V'=V，E'是E的子集，则称G'为G的子图。若G'=G，则称G'为G的子图。
Prim 最小生成树 图解 什么是生成树
子图：G=<V，E>，G'=<V', E'>，为两个图（V为点集，即图中点的集合，E为边集），如果V'是V的子集且E'是E的子集，则G'是G的子图。
如果V'=V，则称G'为G的生成子图
如果G'是无向生成子图且是树的结构，则为生成树
最小生成树
最小生成树：是一张有权无向连通图中边权和最小的生成树
Prim算法：维护一个已经加入最小生成树的点的集合C，每次通过一条边连接一个不在这个点集C的点，直到最后形成一个树形结构
Dist(u)表示u点到点集C中的点的最小距离
每次选择一个到点集C距离最小的点加入点集C，并通过加入的点去更新未加入的点到点集C的最小距离（因为C中多加了一个点），直到n个点全部加入点集C或没有点能够加入（不能构成连通图）。
图解
前言：已经加入点集C的点标记为蓝色，当前加入的点标记为红色，被当前加入的点更新的dist标记为红色。
初始：加入一个初始点A，并通过A更新dist
u A B C D E F dist(u) 0 3 5 inf inf inf加入第二个点B：B到点集C距离最小，并通过B更新dist
u A B C D E F dist(u) 0 3 1 8 3 inf加入第三个点C：C到点集C距离最小，并通过C更新dist
u A B C D E F dist(u) 0 3 1 8 3 inf加入第四个点E：E到点集C距离最小，并通过E更新dist
u A B C D E F dist(u) 0 3 1 2 3 1加入第五个点F：F到点集C距离最小，并通过F更新dist
u A B C D E F dist(u) 0 3 1 2 3 1加入第六个点D：D到点集C距离最小，并通过D更新dist
u A B C D E F dist(u) 0 3 1 2 3 1点全部加入点集，Prim算法结束。
复杂度分析：
总共需要加入n个点，每次需要遍历dist数组找最小值，并通过该点更新未加入点集的dist值，即枚举该点连出的边更新对应的dist，故复杂度为：
O（n*n）+ = O（n*n + m）（mi为每个点连出的边的条数，总和为总边数）
伪代码：
模板题int prim()
{
memset(dis, 127, sizeof(dis)); //初始设置为正无穷
memset(vis, 0, sizeof(vis)); //初始设置点均不在点集中,点集为空
ans = 0, cnt = 0; //初始权值为0
dis[1] = 0; // 1加入点集
while (1)
{
int u = -1;
for (int i = 1; i <= n; i++)
{
if (vis[i] == 0 && dis[i] < (1 << 30)) // i点不在点集中并且与点集中的点联通
{
if (u == -1 || dis[i] < dis[u]) // u==-1 ->第一个点可以更新到点集最近的点
{
u = i; //更新最近的点
}
}
}
if (u == -1)
break; //如果不能找到加入点集的点，则结束算法
cnt++, ans += dis[u]; //点集中点的个数+1，ans加上u连入点集的边权
vis[u] = true; // vis加入点集
for (auto it : a[u])//a[u]为以u连出的边的点的集合，v为相连的点，w为边权
{
dis[it.v] = min(dis[it.v], it.w); //通过点v连出的边更新不在点集的点的dist值
}
}
if (cnt == n)
return ans; //能够加入n个点构成连通图，生成树则返回权值
else
return -1; //不能形成生成树
}
题目链接：最小生成树1 - 题目 - Daimayuan Online Judge
题目描述：
给你一张简单无向连通图，边权都为非负整数。你需要求出它的最小生成树，只需要输出边的权值和即可。
图用以下形式给出：
第一行输入两个整数n,m，表示图的顶点数、边数，顶点编号从1到n。
接下来m行，每行三个整数x,y,z 表示x与y之间有一条边，边权为z。
输入格式：
第一行两个整数n,m。
接下来m行，每行有三个整数，代表一条边。
输出格式：
输出一个数，表示最小生成树的权值和。
数据规模：
对于所有数据，保证2≤n≤1000,n−1≤m≤100000,1≤x,y≤n,x≠y,1≤z≤10000
样例输入：
4 4
1 2 1
2 3 3
3 4 1
1 4 2
样例输出：
4
详见代码：
#include <bits/stdc++.h>
using namespace std;
int dis[100009], cnt, ans, n, m; // dis为点到点集的最小距离，cnt为点集中点的个数，ans为当前的边权和
bool vis[100009];
struct node
{
int v, w;
};
vector<node> a[100009]; //存图
int prim()
{
memset(dis, 127, sizeof(dis)); //初始设置为正无穷
memset(vis, 0, sizeof(vis)); //初始设置点均不在点集中,点集为空
ans = 0, cnt = 0; //初始权值为0
dis[1] = 0; // 1加入点集
while (1)
{
int u = -1;
for (int i = 1; i <= n; i++) //遍历找未加入点集的最小距离的点
{
if (vis[i] == 0 && dis[i] < (1 << 30)) // i点不在点集中并且与点集中的点联通
{
if (u == -1 || dis[i] < dis[u]) // u==-1 ->第一个点可以更新到点集最近的点
{
u = i; //更新最近的点
}
}
}
if (u == -1)
break; //如果不能找到加入点集的点，则结束算法
cnt++, ans += dis[u]; //点集中点的个数+1，ans加上u连入点集的边权
vis[u] = true; // vis加入点集
for (auto it : a[u])
{
dis[it.v] = min(dis[it.v], it.w); //通过点v连出的边更新不在点集的点的dist值
}
}
if (cnt == n)
return ans; //能够加入n个点构成连通图，生成树则返回权值
else
return -1; //不能形成生成树
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
node t1, t2; //无向图存边
t1.v = v, t1.w = w;
a[u].push_back(t1); // u->v 边权为w
t2.v = u, t2.w = w;
a[v].push_back(t2); // v->u 边权为w
}
cout << prim();
}
参考文献：
2022 Namomo Spring Camp Div2 Day10直播课
ending
有什么错误之处欢迎指正！不胜感激！