什么是生成树呢？

一个连通图的生成树是指一个极小连通子图， 它含有图中的全部顶点，但只有足以构成一棵树的n-1条边。

什么是最小生成树？

在一个连通图的所有生成树中，各边的代价之和最小的那棵生成树称为该连通图的最小代价生成树（MST）， 简称最小生成树。

求最小生成树有两种算法，本文讲prim算法。

简略证明

使用反证法证明

设一棵最小生成树T不包含最短边a，将a加入最小生成树T中，书中必定构成一个包含a的回路，而回路中必定有边比a大（因a为最短边），则删除比a大的边得到一棵比原先T更小的树T1，而T1才是最小生成树，则与假设矛盾，证明成立。

prim算法

将树的所有点划分为两个集合U 和 V

每次选一个最小代价的点从V加入U中，然后更新V中的点到U的最小代价，周而复始直到V为空。

1 #include 
     
       2 using namespace std; 3 #define MAX_VERTEX_NUM 20 4 #define INFINTY 32768 5 typedef int AdjType;//权值类型 6 typedef enum{DG, DN, UDG, UDN} GraphKind; 7 typedef char VertexData; 8 //边集 9 typedef struct ArcNode{10     AdjType adj;11     //Other info12 }ArcNode;13 typedef struct{14     VertexData vertex[MAX_VERTEX_NUM];15     ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];16     int vexnum, arcnum;17     GraphKind kind;18 }AdjMatrix;19 struct{20     int adjvex;21     int lowcost;22 }closedge[MAX_VEX_NUM];23 24 MiniSpanTree_Prim(AdjMatrix gn, int u){25     closedge[u].lowcost = 0;26     for(int i = 0; i< gn.vexnum; i++)       //初始化27     if(i != u){28         closedge[i].adjvex = u;29         closedge[i].lowcost = gn.arcs[u][i].adj;30     }31     for(int e = 1; i < = gn.vexnum-1;e++){32         int v = Minium(closedge); //the minium cost from V to U33         int u = closedge[v].adjvex;34        // printf();35        closedge[v].lowcost = 0; //add v to U36        for(int i = 0; i< gn.vexnum; i++)37        if(gn.arcs[v][i].adjgn.arcs[v][i].adj < closedge[i].lowcost){38         closedge[i].lowcost = gn.arcs[v][i].adj;39         closedge[i].adjvex = v;40        }41     }42 43 }