C++蓝白点思想Prim算法（最小生成树

本文主要是介绍C++蓝白点思想Prim算法（最小生成树 - 懒猫老师），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最小生成树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，即结点到自己的边初始化为0else 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;
}