#include <stdio.h>
#include <stdlib.h>
#define Max 50
#define MAX 100
typedef struct MGraph{
char vex[Max];
int arc[Max][Max];
int numVertexes,numEdges;
}MGraph;
void createGraph(MGraph *G)
{
int i,j,k;
printf("請輸入頂點數和邊數：\n");
scanf("%d %d",&G->numVertexes,&G->numEdges);
printf("請輸入頂點的值：\n");
for(i=0;i<G->numVertexes;i++)
scanf("%c",&G->vex[i]);
for(i=0;i<G->numVertexes;j++)
for(j=0;j<G->numVertexes;j++)
G->arc[i][j]=0;
for(i=0;i<G->numEdges;i++)
{
printf("輸入邊（Vi,Vj)的下標i,j和權值\n");
scanf("%d %d %d",&i,&j,&k);
G->arc[i][j]=k;
G->arc[j][i]=k;
}
}
void minispantree_prim(int ad[][Max],int n)
{
int i,j,k,p,q,wm;
p=q=n-1;
ad[p][q]=1;
for(k=0;k<n-1;k++)
{
wm=MAX;
for(i=0;i<n;i++)
if(ad[i][i]=1)
for(j=0;j<n;j++)
if(ad[j][j]=0&&ad[j][j]<wm)
{
wm=ad[i][j];
p=i;q=j;
}
ad[q][q]=1;
printf("%d %d %d\n",p+1,q+1,ad[p][q]);
if(p>q)
ad[p][q]=-ad[p][q];
else
ad[q][p]=-ad[q][p];
}
}
int main()
{
MGraph *G;
int i,j,n,ad[Max][Max];
n=G->numVertexes;
createGraph(G);
for(i=0;i<Max;j++)
for(j=0;j<Max;j++)
ad[i][j]=G->arc[i][j];
minispantree_prim(ad,n);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/228628.html
標籤：C語言
上一篇：請教一個關于gdb除錯的問題