最小生成树minimal-spanning-tree(概念就不具体介绍了)有两种基于不同贪心选择的算法，一个为Prim算法，一个为Kruskal算法。
Prim和Dijkstra算法很像，只是少了些东西。它将结点分为两类，一类是已经选择了的确定的，构建好了的mst的结点，另一类是还没确定的未选择的结点。
流程是这样的：（括号内为权值），U集合：MST的点集合，V-U：未选择的点集合
1.首先初始化开始结点U，然后把所有能够与U相连的边为候选边
这里就是数组初始化操作了;
1 int sum=0;
2 for(int i=1;i<=n;i++)
3 {
4 dis[i]=map[1][i];//初始化所有点到结点1的距离
5 vis[i]=false;//所有点开始都未被访问
6 }
7 vis[1]=true;//结点1标志为true
1
开始时U是结点1,然后找到所有与1相连的边(dist[i][j]!=0)，分别是1-6(10),1-2(28)，所以找出最小的(6<28)那个边对应的结点6加入集合U;
1 for(int i=2;i<=n;i++)
2 {
3 int MIN=INF;//从当前节点u到与u联通的子节点的最小权值
4 int k=-1;
5 for(int j=1;j<=n;j++)//遍历每个点
6 {
7 if(!vis[j]&&dis[j]<MIN)//未被访问且距离还小，那就待定选你了，看看还有没有距离更短的
8 {
9 MIN=dis[j];//更新最小值，这个dis表式这个点到已知mst中一点的最小值
10 k=j;//标记结点号
11 }
12 }
13 vis[k]=true;//u->a->b k->b //置已经访问
14 sum+=MIN;//u->k求生成树的路径和
15 ...
16 ...
17 ...
18 }
然后我们发现，左部分和右部分只有两条边相连了，那么继续找最短边就行6-5(25) <1-2(28),所以选择25的那条边，成这样
再比较1-2(28),5-7(24),5-4(22)，取出最小边是5-4(22),更新图
继续比较选出最短边，这时有4个边要比较了，1-2(28),5-7(24),4-7(18),4-3(12),找出最短边4-3(12),更新图
继续比较4个个边，1-2(28),5-7(24),4-7(18),3-2(16)，找出最短的16,更新图
好了，最后已给点7,应该很容易看出来它是2连接的，因为14是最短的。
所以MST图是这样
后半段的代码是这样的
1 for(int j=1;j<=n;j++)//带已经找到点k的情况下，找结点j
2 {
3 if(!vis[j]&&dis[j]>map[k][j])
4 {//j未访问且 j到mst中点的最小值还大于从k到j的距离，那么就
5 //要更新这段距离
6 dis[j]=map[k][j];//clost[j] = k;
7 }
8 }
看这个图
比如说开始先初始化，dist[6] =10;dist[4]=1,即结点6和4到结点1的最短距离为dist数组，然后我找到了最短路1-4,并且发现原来的1-6(10)大于6-4(5)，所以更新dist[6]=4,他表示结点6到已知MST的某个点的最短的那个距离，也可以将那个点记录在clost数组中，以便需要。
完整代码，其实很简单的
1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int INF=0x3f3f3f3f;
6 const int MAXN=1005;
7 int map[MAXN][MAXN]; //map[i][j] ---- i->j =v
8 int dis[MAXN]; //
9 bool vis[MAXN];
10 int n;
11 void init()
12 {
13 for(int i=0;i<=n;i++)
14 {
15 for(int j=0;j<=n;j++)
16 {
17 if(i!=j)map[i][j]=INF;
18 else map[i][j]=0;
19 }
20 }
21 }
22 int Prim()
23 {
24 int sum=0;
25 for(int i=1;i<=n;i++)
26 {
27 dis[i]=map[1][i];
28 vis[i]=false;
29 }
30 vis[1]=true;
31 for(int i=2;i<=n;i++)
32 {
33 int MIN=INF;//从当前节点u到与u联通的子节点的最小权值
34 int k=-1;//u->v k=v;
35 for(int j=1;j<=n;j++)
36 {
37 if(!vis[j]&&dis[j]<MIN)
38 {
39 MIN=dis[j];
40 k=j;
41 }
42 }
43 vis[k]=true;//u->a->b k->b
44 sum+=MIN;//u->k
45 for(int j=1;j<=n;j++)
46 {
47 if(!vis[j]&&dis[j]>map[k][j])
48 {
49 dis[j]=map[k][j];
50 }
51 }
52 }
53 return sum;
54 }
55 int main()
56 {
57 cin>>n;
58 init();
59 for(int i=1;i<=n;i++)
60 {
61 for(int j=1;j<=n;j++)
62 {
63 int v;
64 cin>>v;
65 if(map[i][j]>v)
66 {
67 map[i][j]=map[j][i]=v;
68 }
69 }
70 }
71 int c;
72 cin>>c;
73 for(int i=1;i<=c;i++)
74 {
75 int a,b;
76 cin>>a>>b;
77 map[a][b]=map[b][a]=0;
78 }
79 /*for(int i=1;i<=n;i++)
80 {
81 int a,b,v;
82 cin>>a>>b>>v;
83 /*if(map[a][b]>v)
84 {
85 map[a][b]=map[b][a]=v;
86 }
87 map[a][b]=v;
88 }*/
89 cout<<Prim()<<endl;
90 return 0;
91 }
View Code