prim

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<string>
 6 #include<vector>
 7 #include<set>
 8 #include<map>
 9 #include<queue>
10 #include<stack>
11 using namespace std;
12 const int inf=0xffffff;
13 const int MAXN=21;
14 int edges[MAXN][MAXN];
15 int lowcost[MAXN];
16 int nearvex[MAXN];
17 int n,m;
18 void prim(int u0)
19 {
20     int i,j;
21     int sum=0;
22     for(i=1;i<=n;i++)
23     {
24         lowcost[i]=edges[u0][i];
25         nearvex[i]=u0;
26     }
27     nearvex[u0]=-1;
28     for(i=1;i<n;i++)            //找出n-1个顶点 
29     {
30         int min=inf;
31         int v=-1;
32         for(j=1;j<=n;j++)
33         {
34             if(nearvex[j]!=-1&&lowcost[j]<min)
35             {
36                 v=j;
37                 min=lowcost[j];
38             }
39         }
40         if(v!=-1)
41         {
42             printf("%d %d %d
",nearvex[v],v,lowcost[v]);
43             nearvex[v]=-1;
44             sum+=lowcost[v];
45             for(j=1;j<=n;j++)
46             {
47                 if(nearvex[j]!=-1&&edges[v][j]<lowcost[j])
48                 {
49                     lowcost[j]=edges[v][j];
50                     nearvex[j]=v;
51                 }
52             }
53         }
54     }
55 }
56 int main()
57 {
58     int i,j;
59     int u,v,w;
60     scanf("%d %d",&n,&m);
61     memset(edges,0,sizeof(edges));
62     for(i=1;i<=m;i++)
63     {
64         scanf("%d%d%d",&u,&v,&w);
65         edges[u][v]=edges[v][u]=w;
66     }
67     for(i=1;i<=n;i++)
68         for(j=1;j<=n;j++)
69         {
70             if(i==j)
71                 edges[i][j]=0;
72             else if(edges[i][j]==0)
73                 edges[i][j]=inf;
74         }
75     prim(1);
76     return 0;
77 }