Prim算法
用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;
}