本文主要是介绍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;
}
路漫漫其修远兮,吾将上下而求索
这篇关于C++蓝白点思想Prim算法(最小生成树 - 懒猫老师)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!