今天写了一个最小生成树的算法，也是为了准备蓝桥杯。题解再说，先专门讨论算法。

最小生成树的算法原理我一直都知道，就是代码一直不会写。简单说一下原理好了。一个无向无环图，每条边上有相应的权值，找到权值的和最小的生成树就是最小生成树。首先将所有的点分为两个集合U，V。其中U是已经找到对应边的点。每次寻找U到V的最短边，并且把这条边在V中的端点加入U。循环下去直到所有的点都被找到。

灵感来源于http://blog.chinaunix.net/uid-25324849-id-2182922.html

下面是代码，注释很清楚了（不连通的点距离是无穷大，自己到自己也是无穷大）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int in = 1000; 7 int main() 8 { 9     int map[5][5] = {
    {
    in,30,in,in,in},{
    30,in,40,40,70},{
    in,40,in,60,62},{
    in,40,60,in,60},{
    in,70,62,60,in}};10     int cost[5];//当前点集合内的点到其他点的最短距离11     int point[5];//在集合内的边（i，point[i]）12     bool visit[5];//该点在不在集合内13     int father[5];//好像没什么用14     int i;15     //先将第一个点加入集合内并且给数组们赋值16     for(i = 0;i < 5;i++)17     {18         cost[i] = map[0][i];19         point[i] = 0;20         visit[i] = false;21         father[i] = 0;22     }23     visit[0] = true;24     int k;25     //有n个顶点就有n-1条边，进行n-1次循环求出这些边26     for(k = 1;k < 5;k++)27     {28         int j = 0;29         int min = in;30         //找出不在集合内的与集合内的点距离最短的点31         for(i = 0;i < 5;i++)32         {33             34             if(!visit[i] && min > cost[i]){min = cost[i];j = i;}35         }36         //将这个点加入集合37         visit[j] = true;38         father[j] = point[j];39         //更新数组们40         for(i = 0;i < 5;i++)41         {42             //对于还不在集合内点，如果与新加入的点的距离小于原来的距离就改变cost数组，43             //并且将该点的边的另一端改为新加入的点44             //i是不在集合里的点，j是刚才加入的点45             if(!visit[i] && cost[i]>map[j][i]){cost[i] = map[j][i];point[i] = j;}46         }47         cout<
          
           <<" "<
           
            <
            
             < 5;i++)51 {52 sum += map[i][point[i]];53 }54 cout<