-
Notifications
You must be signed in to change notification settings - Fork 0
/
作业1-1 prim算法
78 lines (73 loc) · 1.84 KB
/
作业1-1 prim算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int inf=999999;
int map[110][110];//创建map二维数组储存图表
int dis[110];//dis数组记录每2个点间最小权值
int vis[100];//visited数组标记某点是否已访问
int sum;//代表所求的权值之和
void prim(int n)
{
int i,j;
int pos;
memset(vis,0,sizeof(vis));
for(i=1; i<=n; i++)
{
dis[i]=map[1][i];//第一次给dis数组赋值
}
vis[1]=1;//从某点开始,分别标记和记录该点
for(i=1; i<n; i++) //再运行n-1次,剩下的n-1个点
{
//找出最小权值并记录位置
int min=inf;
for(j=1; j<=n; j++)
{
if(!vis[j] && dis[j]<min)
{
min=dis[j];
pos=j;
}
}
if(min>=inf) break;
//最小权值累加
sum+=min;
vis[pos]=1;//标记该点
for(j=1; j<=n; j++)
{
if(!vis[j] && map[pos][j]<dis[j])//更新权值
{
dis[j]=map[pos][j];
}
}
}
}
int main()
{
int n,m;
int i,j;
int a,b,c;//a、b为点,c为两点权值
while(~scanf("%d %d",&n,&m)!=EOF)//循环输入数据n和m的值,n为点数量,m为边数
{
sum=0;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
map[i][j]=inf;//所有权值初始化为最大,代表图上的点没有连线
}
map[i][i]=0;//自身到自身的距离权值为0
}
for(i=1; i<=m; i++)
{
scanf("%d %d %d",&a,&b,&c);//更新点与点之间的权值
if(map[a][b]>c)
map[a][b]=map[b][a]=c;
}
prim(n);
printf("%d\n",sum);
}
return 0;
}