Prim算法

typedef struct
{   
    int     **data;
    int     vertex_num;
    int     edge_num;
} Graph;
//data指向存储数据的存储空间，vertex_num指示顶点的数量，edge_num指示边的数量。



//基于临接矩阵表示的图的Prim算法实现
void Prim(Graph g,int v)
{
    int *flag;
    int i,m,n,min,temp_m,temp_n;

    flag = new int[g.vertex_num];
    memset(flag,0,sizeof(int)*g.vertex_num);

    flag[v]=1;                                    //把顶点v放入集合U
    for(i=0;i<g.vertex_num-1;i++)
    {
        min=INFINITY;
        for(m=0;m<g.vertex_num;m++)
            for(n=0;n<g.vertex_num;n++)
                if((flag[m]+flag[n])==1 && g.data[m][n]<min) // flag[m]+flag[n])==1表示
                {
                    min= g.data[m][n]; //两个顶点中只有一个在集合U中
                    temp_m = m;
                    temp_n = n;
                }
        cout<<temp_m<<"──"<<temp_n<<endl;
        g.data[temp_m][temp_n]=INFINITY;   //不再考虑此边
        flag[temp_m]=1;
        flag[temp_n]=1;
    }

    delete []flag;
}