C++最小生成树
最小生成树：
算法第一步，建图，任何算法均需要考虑，用什么结构去存储，这个算法使用邻接矩阵来存储，有时候输入数据，不是我们期待的那样，所以需要对数据进行一些处理，也就是将图建起来的过程
第二步，辅助数组，对于图G=<V, E>，源点为0(为什么)，dist[i]表示顶点i与已生成的最小生成树之间的最小距离，visited[i]表示dist[i]是否已经确定，即i所在的最小生成数的边是否确定。
第三步，初始化，所有顶点的数据见下，
dist[i] = graph[0][i] (0<= i <= n)
visited[i] = false (0<= i <=n)
visited[0] = true
sum = 0
第四步，找边权最小的点，从所有visited[i]为false的点中找到一个dist[i]值最小的，令x=i，并且找到visited[x]标记为true，如果找不到，算法结束。
第五步，统计边权和，将当前找到的最小边权dist[x]累加到sum上，并且标记visited[x]为true
第六步，更新其余点的最小边权，更新目前最小生成树中所有节点到y的边权，取最小的 dist[y] = min(dist[y], w(x, y))
第七步，回到第四步，继续找边权最小的点
代码分析：
第一步，初始化邻接矩阵
function initEdge(graph, n)
for u-> (0, n-1)
for v-> (0, n-1)
graph[u][v] = inf
第二步，边的添加
function addEdge(graph, u, v, w)
graph[u][v] = min(graph[u][v], w)
graph[v][u] = min(graph[v][u], w)
第三步，建图
addEdge(graph, u1, v1, w1)
addEdge(graph, u2, v2, w2)
...
第四步，框架代码
function Prim(graph, n, dist)
visited[]
sum=0
PrimInit(n, visited, dist)
while true
u = PrimFindMin(n, visited, dist)
if u == -1 return sum
sum += dist[u]
PrimUpdate(graph, n, u, visited, dist)
第五步，Prim初始化
function PrimInit(n, visited,dist)
for i-> (0, n-1)
visited[i] = false
dist[i] = graph[0][i]
visited[0] = true
第六步，Prim找边权最小的点
function PrimFindMin(n, visited, dist)
u = -1
for i -> (0, n-1)
if(visited[i]) continue
if u == -1 or dist[i] < dist[u]
u = i
return u
第七步 Prim 更新
function PrimUpdate(graph, n, u, visited, dist)
visited[u] = true
for i -> (0, n-1)
if visited[i] continue
dist[i] = min(dist[i], graph[u][i])
代码练习 1 对应力扣 城邦 代码见下
#include <iostream>
using namespace std;
#define maxn 2022
#define edgeType int
#define inf 1000000000
void initEdge(int n, edgeType graph[maxn][maxn]){
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
graph[i][j] = (i == j ? 0:inf);
}
}
}
void addEdge(edgeType graph[maxn][maxn], int u, int v, edgeType w){
if(w < graph[u][v]){
graph[u][v] = w;
}
if(w < graph[v][u]){
graph[v][u] = w;
}
}
edgeType prim(int n, edgeType graph[maxn][maxn]){
int visited[maxn] = {0};
edgeType dist[maxn];
edgeType sum = 0;
for(int i=0; i<n; ++i){
dist[i] = graph[0][i];
}
visited[0] = 1;
while(1){
edgeType minDist = inf;
int minIndex = -1;
for(int i=0; i<n; ++i){
if(!visited[i] && dist[i] < minDist){
minDist = dist[i];
minIndex = i;
}
}
if(minIndex == -1){
break;
}
sum += minDist;
visited[minIndex] = 1;
for(int i=0; i<n; ++i){
if(!visited[i] && graph[minIndex][i] < dist[i]){
dist[i] = graph[minIndex][i];
}
}
}
for(int i=0; i<n; ++i){
if(!visited[i]){
return -1;
}
}
return sum;
}
edgeType graph[maxn][maxn];
int main()
{
initEdge(2021, graph);
for(int i=1; i <= 2021; ++i){
for(int j=i+1; j<=2021; ++j){
int u = i, v = j;
edgeType w = 0;
while(u || v){
if(u%10 != v%10){
w += u%10 + v%10;
}
u /= 10;
v /= 10;
}
addEdge(graph, i-1, j-1, w);
}
}
cout << prim(2021, graph) << endl;
// 请在此输入您的代码
return 0;
}代码练习 2 对应蓝桥云课 通电 代码见下
#include <iostream>
#include <cmath>
using namespace std;
#define maxn 1001
#define edgeType double
#define inf 1000000000
void initEdge(int n, edgeType graph[maxn][maxn]){
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
graph[i][j] = (i == j ? 0:inf);
}
}
}
void addEdge(edgeType graph[maxn][maxn], int u, int v, edgeType w){
if(w < graph[u][v]){
graph[u][v] = w;
}
if(w < graph[v][u]){
graph[v][u] = w;
}
}
edgeType prim(int n, edgeType graph[maxn][maxn]){
int visited[maxn] = {0};
edgeType dist[maxn];
edgeType sum = 0;
for(int i=0; i<n; ++i){
dist[i] = graph[0][i];
}
visited[0] = 1;
while(1){
edgeType minDist = inf;
int minIndex = -1;
for(int i=0; i<n; ++i){
if(!visited[i] && dist[i] < minDist){
minDist = dist[i];
minIndex = i;
}
}
if(minIndex == -1){
break;
}
sum += minDist;
visited[minIndex] = 1;
for(int i=0; i<n; ++i){
if(!visited[i] && graph[minIndex][i] < dist[i]){
dist[i] = graph[minIndex][i];
}
}
}
for(int i=0; i<n; ++i){
if(!visited[i]){
return -1;
}
}
return sum;
}
int n;
int x[maxn], y[maxn], h[maxn];
edgeType graph[maxn][maxn];
int SQR(int x){
return x*x;
}
int main()
{
cin >> n;
for(int i=0; i<n; ++i){
cin >> x[i] >> y[i] >> h[i];
}
initEdge(n, graph);
for(int i=0; i<n; ++i){
for(int j = i+1; j<n; ++j){
edgeType w = sqrt(SQR(x[i] - x[j]) + SQR(y[i] - y[j])) + SQR(h[i] - h[j]);
addEdge(graph, i, j, w);
}
}
// 请在此输入您的代码
printf("%.2lf\n", prim(n, graph));
return 0;
}代码练习 3，对应蓝桥云课 繁忙的都市，代码见下
#include <iostream>
#include <cmath>
using namespace std;
#define maxn 300
#define edgeType int
#define inf 1000000000
void initEdge(int n, edgeType graph[maxn][maxn]){
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
graph[i][j] = (i == j ? 0:inf);
}
}
}
void addEdge(edgeType graph[maxn][maxn], int u, int v, edgeType w){
if(w < graph[u][v]){
graph[u][v] = w;
}
if(w < graph[v][u]){
graph[v][u] = w;
}
}
edgeType prim(int n, edgeType graph[maxn][maxn]){
int visited[maxn] = {0};
edgeType dist[maxn];
edgeType sum = 0;
for(int i=0; i<n; ++i){
dist[i] = graph[0][i];
}
visited[0] = 1;
while(1){
edgeType minDist = inf;
int minIndex = -1;
for(int i=0; i<n; ++i){
if(!visited[i] && dist[i] < minDist){
minDist = dist[i];
minIndex = i;
}
}
if(minIndex == -1){
break;
}
sum += minDist;
visited[minIndex] = 1;
for(int i=0; i<n; ++i){
if(!visited[i] && graph[minIndex][i] < dist[i]){
dist[i] = graph[minIndex][i];
}
}
}
for(int i=0; i<n; ++i){
if(!visited[i]){
return -1;
}
}
return sum;
}
edgeType graph[maxn][maxn];
#define maxm 100001
int n, m;
int u[maxm], v[maxm], c[maxm];
int check(int max){
initEdge(n, graph);
for(int i=0; i<m; ++i){
if(c[i] <= max){
addEdge(graph, u[i] - 1, v[i] - 1, c[i]);
}
}
return prim(n, graph) >= 0;
}
int main()
{
cin >> n >> m;
for(int i=0; i<m; ++i){
cin >> u[i] >> v[i] >> c[i];
}
int l = 0, r = 10000;
int ans = -1;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)){
r = mid - 1;
ans = mid;
}else{
l = mid + 1;
}
}
cout << n - 1 << ' ' << ans << endl;
// 请在此输入您的代码
return 0;
}
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
19
0- 0
已为社区贡献9条内容
所有评论(0)