prim贪心算法

一最小生成树的条件

树上边：在最小生成树上的边

非树上边：不在最小生成树上的边

树上路径：最小生成树上两点间的唯一路径

路径最优：任一非树上边的权重都大于它所对应的树上路径上的每条边的权重。
（否则用该边形成的生成树权重更小）

割边：任意树上边把树分为两部分，连接该两部分的边为割边

割最优：任一树上边的权重都小于它所对应的割集中每条边的权重。
（否则用比该边小的割边来连接成的生成树更小）

二  PRIM

PRIM：根据割最优

算法3：（就是PRIM）

假设现在已经有了一棵包含某些点的树了，
要把它和剩下的点连起来，从该树有许多割边指出，
那么根据割最优条件，选取最小的一个，一定在树上，
同时该树上的点增加一个。

初始的时候随便选一个点就可以了。

#include
#define n 6
typedef struct
{
    int from,end;
    float length;
}
edge;
edge T[n-1];
float dist[n][n] =
{
    100000,10,100000,100000,19,21,
    10,100000,5,6,100000,11,
    100000,5,100000,6,100000,100000,
    100000,6,6,100000,18,14,
    19,100000,100000,18,100000,33,
    21,11,100000,14,33,100000
};
//求最小生成树就是找n-1条边
void prime(int i)        //i是最小生成树的根
{
    int j,k,m,v;
    float min,max = 100000;
    float d;
    edge  e;
    v = i;
    //初始化这n-1条边为从根出发的边,尽管某些边不存在
    for(j=0;j < n-1;j++)    //共有n -1 条边
    {
        T[j].from = v;    //边的一个端点
        if(j>=v)
        {    
            T[j].end = j+1;        //另一个端点不能是自己,整体右移一位,构成完成的边,因为顶点比边数目多一个
            T[j].length = dist[v][j+1];
        }else{
            T[j].end = j;
            T[j].length = dist[v][j];
        }
    }
    //正式找边
    for(k=0;k    {
        min = max;
        //找到从根开始的最短的边,初始化最小树第一条边,根结点不在结束顶点之列
        for(j = k;j            if(T[j].length            {
                min = T[j].length;
                m = j;
            }
        //将第k短的边交换到数组的前面，相当于入队, 第一次from都是根i;
        e = T[m];        //结构体复制，其实就是bit-copy
        T[m] = T[k];
        T[k] = e;

        v = T[k].end;        //要加入最小树的顶点
        //更新边集中候选边,新顶点引入的边只有到相同的顶点(即end)距离较大时才会更新
        for(j=k+1;j        {
            d = dist[v][ T[j].end ];
            if(d < T[j].length)
            {
                T[j].length =d;
                T[j].from  =v;
            }
        }
    }
}
int main()
{
    int i;
    prime(2);
    for(i=0;i        printf("%d--%.0f-->%d\n",T[i].from,T[i].length,T[i].end);
    return 0;
}