Prim算法如何应用于无向图以构建最小生成树？

本文共计483个文字，预计阅读时间需要2分钟。

输入+第1行：2个数字N，M中问用空格分隔（N为点的数量，M为边的数量）（2<=N<=1000，1<=M<=50000）第2-M+1行：每行3个数字SEW，分别代表边的起点S、终点E和权重W。（1<=S,E<=N，1<=W<=10000）输出：输出最小生成树的边，包括起点、终点和权重。

输入

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2<=N<=1000,1<=M<=50000) 第2-M+1行：每行3个数SEW，分别表示M条边的2个顶点及权值。(1<=S,E<=N，1<=W<=10000)

输出

输出最小生成树的所有边的权值之和。

输入示例

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

输出示例

37

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 1005
#define INF 0x7fffffff

int N,M,S,E,W;
vector<vector<int> > val(MAX,vector<int>(MAX,INF));

long long prim(){
long long res=0;
vector<bool> vis(MAX,false);
vector<int> min(MAX,INF);
min[1]=0;
for(int i=1;i<=N;i++){
int j,k;
for(k=-1,j=1;j<=N;j++)
if(!vis[j]&&(k==-1||min[j]<min[k]))
k=j;
vis[k]=1;
res+=min[k];
for(int i=1;i<=N;i++)
if(!vis[i]&&val[k][i]<min[i])
min[i]=val[k][i];
}
return res;
}
int main(){

cin>>N>>M;
for(int i=0;i<M;i++){
cin>>S>>E>>W;
val[S][E]=val[E][S]=W;
}
cout<<prim()<<endl;
return 0;
}