prim算法实现，数据存储时需注意对称点，比如a[2][3]和a[3][2]是相同的，本体难点在于怎么判断是否为环，我的想法是假设通路，递归DFS（深度优先）找寻是否能找回原点，是则把此通路置为-1（也就是无联通）,否则可存入最小生成树数组b[][]中
以下是程序代码：
#include<stdio.h>
#define M 7
int a[M][M];//初始数组
int b[M][M];//最小二成树数组
int visited[M];
int x,y;
void init()//初始化连通图
{
inti,j;
for(i=1;i<M;i++)
for(j=1;j<M;j++)
{
b[i][j]=-1;
a[i][j]=-1;
}
for(i=0;i<M;i++)
visited[i]=0;
visited[1]=1;
a[1][2]=6;
a[1][4]=5;
a[1][3]=1;
a[2][3]=5;
a[2][5]=3;
a[3][4]=5;
a[3][6]=4;
a[3][5]=6;
a[4][6]=2;
a[5][6]=6;
for(i=1;i<M;i++)
for(j=1;j<M;j++)
{
if(a[i][j]!=0)
a[j][i]=a[i][j];
}
}
void print(int x[M][M])
{
inti,j;
for(i=1;i<M;i++)
{
for(j=1;j<M;j++)
printf("%2d",x[i][j]);
printf("\n");
}
printf("\n");
}
int judge(int sa,int sb)
{
inti;
for(i=1;i<M;i++)
{
if(i!=sa&&b[sb][i]!=-1){
judge(sb,i);
}
if(sa==x&&sb==y){return1;}
}
}
void prim()
{
inti,j,fla,min;
min=99999;
for(i=1;i<M;i++)
{
if(visited[i])
{
for(j=1;j<M;j++)
{
// printf("i=%d,j=%d,a[i][j]=%d,min=%d\n",i,j,a[i][j],min);
if(b[i][j]==-1&&a[i][j]!=-1&&a[i][j]<min)
{
x=i;
y=j;
min=a[i][j];
}
}
// printf("\n%d\n",i);
}
}
// printf("\n%d %d %d\n",x,y,min);
fla=0;
for(i=1;i<M;i++)
{
if(i!=x&&b[y][i]!=-1){
fla=judge(y,i);
}
}
if(fla==0){b[y][x]=min;b[x][y]=min;visited[y]=1;}
else{a[y][x]=-1;a[x][y]=-1;prim();}
}
int main()
{
inti;
init();
printf("原始图\n");
print(a);
for(i=1;i<M-1;i++)
prim();
printf("最小生成树\n");
print(b);
return0;
}