最小生成树Prim算法（C++蓝白点思想）
- 一、知识储备
- 1.图的构造
- 2.蓝白点思想
- 二、代码实现
一、知识储备
我们都知道，最小生成树的定义为：是原图的极小连通子图，包含图中所有结点，最重要的是保持图连通最少的边。❤️小白发文，若有不足欢迎大佬来斧正~
1.图的构造
构造一个对象时，我们需要先了解清除其含有什么特征、什么特性，再去进行构造。在这里，图的构造也不例外，图具有多个顶点那我们就开辟个顶点数组，同时需要开辟个蓝白标记的数组（相当于两个集合的概念），需要个邻接矩阵储存图的边权，还需要知道创造图时所需的顶点数、边数。 好了说了一堆废话，让我们讲下一个吧💥
2.蓝白点思想
☁️所谓蓝白点思想，无非跟你们看死板的书所说的集合类似，但是蓝白点思想更加形象，白点代表已经用Prim方法连通了的结点，而蓝点则代表需要连通的结点。 每洗白一个蓝点，就需要更新每个蓝点到白点集团的最小值。下面展示的是简单例子部分洗白过程图：
二、代码实现
🌟注：该代码实现的结点vertex是char型，有需要可自行修改类型，后续有时间会为 实现构造出一颗最小生成树(树的结构) 再更新文章。
#include <iostream>
#include <algorithm>
#define ll 9999 //相当于无穷大
using namespace std;
struct AMGraph
{
char *vertices; //顶点表
int *visited; //蓝白点标志
int **arcWeight; //邻接矩阵
int currVex, currArc; //当前的顶点数 、边数
};
int get_Index(const AMGraph &G, char u)
{
for(int i = 0; i < G.currVex; i++)
if(u == G.vertices[i]) return i; //获得顶点在顶点数组中的下标
return -1;
}
void createUND(AMGraph &G)
{
cout << "输入图的顶点个数和边数：";
cin >> G.currVex >> G.currArc;
G.vertices = new char[G.currVex];
G.visited = new int[G.currVex];
cout << "输入顶点的值(char类型)：";
for(int i = 0; i < G.currVex; i++){
cin >> G.vertices[i];
}
//动态邻接矩阵开辟空间，同时进行初始化
G.arcWeight = new int*[G.currVex];
for(int i = 0; i < G.currVex; i++){
G.arcWeight[i] = new int[G.currVex];
for(int j = 0; j < G.currVex; j++)
if(i == j) G.arcWeight[i][j] = 0; //邻接矩阵中主对角线全为0，即结点到自己的边初始化为0
else G.arcWeight[i][j] = ll; //除了上条语句情况其余邻接矩阵的位置的权值初始化为无穷大
}
fill(G.visited, G.visited+G.currVex, 1); //填充一维数组，初始化每个顶点的标记都为1（即蓝点）
char v1, v2;
int i, j, power;
cout << "输入哪两个顶点对应的边权值是多少：";
for(int k = 0; k < G.currArc; k++){
cin >> v1 >> v2 >> power;
i = get_Index(G, v1);
j = get_Index(G, v2);
G.arcWeight[i][j] = power; //这里是 i 行 j 列
G.arcWeight[j][i] = power; //这里是 j 列 i 行
}
return;
}
void Prim(AMGraph& G)
{
int Min[G.currVex];
fill(Min, Min+G.currVex, ll);
Min[0] = ll; // min[0]定义为无穷大才能实现每 i 轮的 Min 的初始化
int MST = 0;
cout << "洗白点的顺序：";
for(int i = 0; i < G.currVex; i++)
{
int w = 0;
for(int j = 0; j < G.currVex; j++)
if(G.visited[j] && Min[w] > Min[j]) { //找出当前离白点集团最近的蓝点
w = j;
}
G.visited[w] = 0; //洗白
cout << G.vertices[w] << " ";
if(w != 0) // 权值累加时排除刚开始节点的权值（因为刚开始的节点权值为无穷大 ll）
MST += Min[w]; //权值累加
for(int k = 0; k < G.currVex; k++)
if(G.visited[k] && G.arcWeight[w][k] < Min[k]){
Min[k] = G.arcWeight[w][k]; //更新每个蓝点到白点集团的最小值
}
}
cout << endl;
cout << "连通图最小边权总和：" << MST << endl;
}
int main()
{
AMGraph G; //构造图
createUND(G); //初始化无向图
Prim(G);
return 0;
}
Input
输入图的顶点个数和边数：6 10
输入顶点的值(char类型)：A B C D E F
输入哪两个顶点对应的边权值是多少：
A B 6
A C 1
A D 5
B C 5
B E 3
C E 6
C D 5
D F 2
E F 6
C F 4
Output
洗白点的顺序：A C F D B E
连通图最小边权总和：15
2022年1月8号更新：上面的思想用于加深理解，但算法竞赛中更常用下列算法模板，若有需要可继续往下看。
👉对应题目：2021年蓝桥杯十二届B组第二次题目——城邦
👉模板练习：最小生成树
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 2030, M = N * N / 2;
int n = 2021;
int g[N][N]; // g[i][j] 表示点i和点j之间边的长度
int dist[N]; // dist[i] 表示点i到当前集合的最短边的长度
bool st[N]; // st[i] 表示点i是否在当前生成树集合中
int get(int x, int y){
int res = 0;
while(x || y){
int a = x % 10, b = y % 10;
if(a != b) res += a + b;
x /= 10, y /= 10;
}
return res;
}
int prim()
{
int res = 0;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= n; i++){ //迭代n次
int t = -1;
for(int j = 1; j <= n; j++) //当前蓝点集合中所有距离白点最小的点
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j; //此时t存得是当前距离集合最小得点
st[t] = true;
//当前点不是第一个点，并且当前距离最近的点到集合距离是正无穷，因此该图不联通
if(i != 1 && dist[t] == INF) return INF;
//这里和上面其实可以不用判断当前是否为第一个点，因为我们将dist[1] = 0;
//如果未dist[1]初始化，则要判断是否为第一个点
if(i != 1) res += dist[t];
for(int j = 1; j <= n; j++)
if(!st[j]) dist[j] = min(dist[j], g[t][j]); //dist[i]代表着i到集合的距离，与dijkstra不同
}
return res;
}
int main(){
memset(g, 0x3f, sizeof g);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if(i == j) continue;
g[i][j] = g[j][i] = get(i, j);
}
cout << prim() << endl;
return 0;
}
路漫漫其修远兮，吾将上下而求索
