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 1000000000void 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 1000000000void 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 1000000000void 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;
}