#include <stdio.h>

#define inf 9999

#define max 40

prim(int g[][max],int n)

{int lowcost[max],closest[max];

int i,j,k,min;

for(i=2;i<=n;i++) //n個頂點，n-1條邊

{lowcost[i]=g[1][i]; //初始化

closest[i]=1; //頂點未加入到最小生成樹中

}

lowcost[1]=0; //標志頂點1加入U集合

for(i=2;i<=n;i++) //形成n-1條邊的生成樹

{min=inf;

k=0;

for(j=2;j<=n;j++) //尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊

if((lowcost[j]<min)&&(lowcost[j]!=0))

{min=lowcost[j];

k=j;

}

printf("(%d,%d)%d\t",closest[k],k,min);

lowcost[k]=0; //頂點k加入U

for(j=2;j<=n;j++) //修改由頂點k到其他頂點邊的權值

if(g[k][j]<lowcost[j])

{lowcost[j]=g[k][j];

closest[j]=k;

}

printf("\n");

}

}





int adjg(int g[][max]) //建立無向圖

{int n,e,i,j,k,v1,v2,weight;

printf("輸入頂點個數，邊的條數：");

scanf("%d,%d",&n,&e);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

g[i][j]=inf; //初始化矩陣，全部元素設為無窮大

for(k=1;k<=e;k++)

{printf("輸入第%d條邊的起點，終點，權值:",k);

scanf("%d,%d,%d",&v1,&v2,&weight);

g[v1][v2]=weight;

g[v2][v1]=weight;

}

return(n);

}





void prg(int g[][max],int n) //輸出無向圖的鄰接矩陣

{int i,j;

for(i=0;i<=n;i++)

printf("%d\t",i);

for(i=1;i<=n;i++)

{printf("\n%d\t",i);

for(j=1;j<=n;j++)

printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);

}

printf("\n");

}





main()

{int g[max][max],n;

n=adjg(g);

printf("輸入無向圖的鄰接矩陣:\n");

prg(g,n);

printf("最小生成樹的構造:\n");

prim(g,n);

}

  回復  更多評論