最小生成树

　　最小生成树就是将一个图中的若干边去掉，使之成为一棵树，这棵树的各条边的权值之和最小。

　　构造最小生成树有两个典型的算法——Prim算法和Kruskal算法。下面就分别介绍这两个算法。两个算法都是开始将各个顶点孤立，然后依次选取若干边将顶点连接起来构成一棵树。

Prim算法

　　算法的流程大致如下：

（1）选取任意顶点V_{0，将其放入已访问集合V（未访问集合为U）。}

（2）遍历已访问集合中所有顶点，选取到未访问集合中的顶点距离最小的点加入访问集合。

（3）当所有的顶点都在已访问集合中时，算法结束。

因此，我们定义lowcost数组记录V到U中的i顶点中的距离，定义closeset数组记录i顶点是由哪一个顶点延伸出来的。以此来构造最后的生成树。

1 #include
     
       2 #define MAXSZIE 100 3 typedef struct Vertex 4 { 5     int num; 6 } Vertex; 7 typedef struct MGraph 8 { 9     int n,e;10     int edges[MAXSZIE][MAXSZIE];11     Vertex vex[MAXSZIE];12 } MGraph;13 int BTree[MAXSZIE][MAXSZIE];14 MGraph create()15 {16     int n,e;17     int a,b,val;18     MGraph g;19     scanf("%d%d",&n,&e);20     g.n=n;21     g.e=e;22     for(int i=0; i
     

　　如上述代码所示，我们使用邻接矩阵表示图，不连通的顶点之前的权值为无穷大。

　　依次看所有的节点，每次选取最小的边进行扩展，所以就是每次选择一个顶点加入到最小生成树中，当我们将所有顶点遍历一遍（最外层循环）的时候，算法结束。

　　每次扩展节点，我们选取到未扩展集合权值最小的边，也就是选取lowcost中值最小的，记录其顶点坐标k。延伸出k的closeset的值就是k的父节点。

　　每扩展完一次，就要对lowcost数组和closeset数组进行更新，对应代码的66~70行，也就是说，如果新延伸的节点k到未访问集合的距离如果更短，那么未访问集合中下一个延伸的节点肯定是由k延伸出去的，否则是由其他点延伸出去的。这个显然啊，因为下一次也是从V的邻接边中找最小的，你从k出发，到未访问的节点小于你之前的lowcost数组中的值，那么下一次延伸的节点必然是从k出去的（从其他节点到未访问集合的距离已经被更新）。

　　说的有点乱，举个栗子。

　　　　　　　　　　　　　　　　　　　　　　　　

　　一开始，我们将0标记为已访问。所有的节点一开始默认从0延伸出去。此时，lowcost[1]=5，下一次，找到了2节点（就是上边所说的k），2加入到集合中，此时，从2到1的距离为3，比lowcost[1]=5要小，所以，1肯定不能由0延伸出去，肯能是从2延伸，那么就要更新1的lowcost值和closeset值，当我们扩展1的时候，2通过closeset就直接找到了其父节点。

　　对于Prim算法的时间复杂度，很明显是O（n²）的。

Kruskal算法

　　算法的大致流程如下：

（1）将所有的边按从小到大排序。

（2）从小到大依次选择边构成树，注意不能成环。

（3）所有的边遍历一遍后，算法结束

将节点依次加入集合中构成树，需要用到并查集。

1 #include
     
        2 #define MAXSZIE 100  3 typedef struct Vertex  4 {  5     int num;  6 } Vertex;  7 typedef struct MGraph  8 {  9     int n,e; 10     int edges[MAXSZIE][MAXSZIE]; 11     Vertex vex[MAXSZIE]; 12 } MGraph; 13 int BTree[MAXSZIE][MAXSZIE]; 14 typedef struct Road 15 { 16     int a,b; 17     int weight; 18 } Road; 19 Road r[MAXSZIE]; 20 int count=0; 21 MGraph create() 22 { 23  24     int n,e; 25     int a,b,val; 26     MGraph g; 27     scanf("%d%d",&n,&e); 28     g.n=n; 29     g.e=e; 30     for(int i=0; i
      
       r[j].weight) 78             { 79                 tempr=r[j]; 80                 r[j]=r[i]; 81                 r[i]=tempr; 82             } 83         } 84     } 85 } 86 void Kruskal(MGraph g) 87 { 88     getSort(g); 89     int x,y; 90     for(int i=0; i
      
     

　　算法很简单，只要对边进行排序，然后依次合并就可以了，这里就不举栗子了。所以算法的时间复杂度与排序算法的时间复杂度相同。