全新.txt

对一个带权无向图

#include<stdio.h>
#include<stdlib.h>
#define M 20
#define MAX 20
typedef struct 
{
 int begin;
 int end;
 int weight;
}EdgeType;
typedef struct
{
 int adj;
 int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
 AdjMatrix arc;
 int vexnum, arcnum;
}MGraph;
void CreatGraph(MGraph *);
void sort(EdgeType* ,MGraph *);
void MiniSpanTree(MGraph *);
int  Find(int *, int );

void CreatGraph(MGraph *G)
{
 int i, j,n, m;
 printf("bianshuhedingdianshu:");
 scanf("%d %d",&G->arcnum,&G->vexnum);
 
    for (i = 1; i <= G->vexnum; i++)
 {
  for ( j = 1; j <= G->vexnum; j++)
  {
   G->arc[i][j].adj = G->arc[j][i].adj = 0;
  }
 }
 for ( i = 1; i <= G->arcnum; i++)
 {
  printf("\nshuruyoubiandedingdian:");
  scanf("%d %d",&n,&m);
  while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum)
  {
   printf("输入的数字不符合要求 请重新输入:");
   scanf("%d%d",&n,&m);
  }
     
  G->arc[n][m].adj = G->arc[m][n].adj = 1;
  getchar();
  printf("\n%dhe%djianquanzhi:", n, m);
  scanf("%d",&G->arc[n][m].weight);
 }
    
 printf("linjiejuzheng:\n");
 for ( i = 1; i <= G->vexnum; i++)
 { 
  for ( j = 1; j <= G->vexnum; j++)
  {
      printf("%d ",G->arc[i][j].adj);
  }
     printf("\n");
 }
}
void sort(EdgeType EdgeTypes[],MGraph *G)
{
 int i, j,t;
 for ( i = 1; i < G->arcnum; i++)
 {
  for ( j = i + 1; j <= G->arcnum; j++)
  {
   if (EdgeTypes[i].weight > EdgeTypes[j].weight)
   {
   t = EdgeTypes[i].begin;
    EdgeTypes[i].begin = EdgeTypes[j].begin;
    EdgeTypes[j].begin = t;
    t = EdgeTypes[i].end;
    EdgeTypes[i].end = EdgeTypes[j].end;
    EdgeTypes[j].end = t;
    t = EdgeTypes[i].weight;
    EdgeTypes[i].weight = EdgeTypes[j].weight;
    EdgeTypes[j].weight = t;
   }
  }
 }
    
 printf("paixuzihou:\n");
 for (i = 1; i <=G->arcnum; i++)
 {
     printf("<< %d, %d >>   %d\n", EdgeTypes[i].begin, EdgeTypes[i].end, EdgeTypes[i].weight);
 }
}

void MiniSpanTree(MGraph *G)
{
 int i, j, n, m;
 int k = 1;
    int father[M];
 EdgeType EdgeTypes[M];
 
 for ( i = 1; i < G->vexnum; i++)
 {
  for (j = i + 1; j <= G->vexnum; j++)
  {
   if (G->arc[i][j].adj == 1)
   {
    EdgeTypes[k].begin = i;
    EdgeTypes[k].end = j;
    EdgeTypes[k].weight = G->arc[i][j].weight;
       k++;
   }
   
  }
 }
        
    sort(EdgeTypes, G);
    for (i = 1; i <= G->arcnum; i++)
 {
  father[i] = 0;
 }
    printf("zuixiaoshengchengshu:\n");
 for (i = 1; i <= G->arcnum; i++)
 {
  n = Find(father, EdgeTypes[i].begin);
  m = Find(father, EdgeTypes[i].end);
  if (n != m)
  {
     father[n] = m;
     printf("<< %d, %d >>   %d\n", EdgeTypes[i].begin, EdgeTypes[i].end, EdgeTypes[i].weight);
  }
 }
}
int Find(int *father, int f)
{
 while ( father[f] > 0)
 {
  f = father[f];
 }
    return f;
}
int main(void)
{
 MGraph *G;
 int q;
 G = (MGraph*)malloc(sizeof(MGraph));
 if (G == NULL)
 {
  printf("memory allcation failed,goodbye");
  exit(1);
 }
do{
    
 CreatGraph(G);
    MiniSpanTree(G);
printf("Do you want again?(1 or 0):");
scanf("%d",&q);}while(q);
   
 system("pause");
 return 0;

getch();
}