边的权值之和最小的生成树Minimum-Spanning-Tree
假设G=(V, E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边(u, v)的最小生成树。
任意一个生成树T，添加一条边e则会产生回路，删除该回路中的任一条边，则又恢复为生成树，若e小于删除的那条边，则得到一个更小的生成树。
在建立的时候，所添加的边都为避免生成回路的可添加的边中最小的，则最后生成的生成树是不可改进的。任意边换进去得到的回路中，换进去的那条边一定是最大的。
采用贪心算法

GENERIC_MST(G)
{
    T=NULL;
    while T未形成一棵生成树;
        do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
            T=TU(u, v);
}

Prim

初始化：向空树T=(VT, ET)中添加图G=(V, E)的任一顶点u0，使VT={u0}，ET=空集
循环（重复下列操作至VT=V)：从G中选择满足{(u, v)|u∈VT，v∈V-VT}且具有最小权值的边(u, v)，把v加入VT，这条边加入ET
时间复杂度O(|V|^2)不依赖于|E|，因此适用于求解边稠密的图的最小生成树。

struct{
    VertexType adjvex; //与哪个VT中的点相连
    VRType lowcost;  //权值
}closeedge[MAX_SIZE];
//数组下标与图的点数组下标一致

void MiniSpanTree(MGraph G, VertexType u)
{
    k=LocateVex(G, u);
    for(j=0;j<G.vexnum;++j)
        if(j!=k)
            closeedge[j]={u, G.arcs[k][j];
    closeedge[k].lowcost=0;
    for(i=0;i<G.vexnum;++i)
    {
        k=minimum(closeedge);    //下一个要加入生成树的点
        printf(closeedge[k].adjvex, G.vexs[k]);    //输出生成树上一条边
        closeedge[k].lowcost=0;    //将k加入VT
        for(j=0;j<G.vexnum;++j)    //修改其它顶点的最小边
            if(G.arcs[k][j]<closeedge[j].lowcost)
                closeedge[j]={G.vexs[k], G.arcs[k][j]}
}

Kruskal

Prim是选顶点，Kruskal是选边
初始化：VT=V，ET=空集，每个顶点构成一棵独立的树
循环（重复下列操作至T是一棵树）：按G的边的权值递增顺序依次从E-ET中选择一条边，若这条边加入T后不构成回路，则加入ET，知道ET中有n-1条边。
用类似于并查集的算法，通常采用堆来存放边的集合，每次选择最小权值的边只需O(log|E|)
时间复杂度O(|E|log|E|)，适用于边稀疏而顶点较多的图。

Typedef struct{
    int vi, vj, w;
}edgeset[MAX_SIZE_E];

int set[MAX_SIZE_V];

int FindSet(int set[], int v)
{
    i=v;
    while(set[i]>0) i=set[i];
    return i;
}

void krusal(edgeset get, int n, int e)
{
    //get为权按从小到大到顺序排序的边集数组
    for(i=0;i<=n;++i)  set[i]=0;
    i=1; //get中的下标
    j=1; //生成树中的边数
    while(j<n)//一共要获得n-1条边
    {
        v=FindSet(set, get[i].vi);
        w=FindSet(set, get[i].vj);
        if(v!=w){
            //vi,vj不在同一集合，不会构成回路
            cout<<get[i].vi<<","<<get[i].vj<<endl;
            set[v]=w;
            ++j;
        }
        ++i;
    }
}