最小生成树.cpp

最小生成树问题 问题描述：若要在ｎ个城市之间架设通讯网络

#include<stdio.h>
#include<stdlib.h>
#define M 30
#define MAX 100

typedef struct                        
{
 int begin;
 int end;
 int weight;                          
}edge;

typedef struct
{
 int adj;
 int weight;
}AdjMatrix[MAX][MAX];

typedef struct
{
 AdjMatrix arc;
 int vexnum, arcnum;                  
}MGraph;

void CreatGraph(MGraph *);             

void sort(edge* ,MGraph *);            
void MiniSpanTree(MGraph *);           
int  Find(int *, int ); 
	
void Swapn(edge *, int, int);           

   

   void CreatGraph(MGraph *G)           
{
 int i, j,n, m;

 printf("请输入城市的数目以及边的数目：");
 scanf("%d %d",&G->vexnum,&G->arcnum);
 
    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("\n请输入边的起始城市和终点城市：");
  scanf("%d %d",&n,&m);
  while(n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
  {
printf("                                  \n");
printf("                                  \n");
   printf("输入的数字不符合要求 请重新输入：");
   scanf("%d%d",&n,&m);
  }
     
     G->arc[n][m].adj = G->arc[m][n].adj = 1;
     getchar();
  printf("\n请输入%d与%d之间的权值:   ", n, m);
  scanf("%d",&G->arc[n][m].weight);     
 }
    
 

}
 

    void sort(edge edges[],MGraph *G)     
{
 int i, j;

 for ( i = 1; i < G->arcnum; i++)
 {
  for ( j = i + 1; j <= G->arcnum; j++)
  {
   if (edges[i].weight > edges[j].weight)
   {
    Swapn(edges, i, j);
   }
  }
 }
 printf("                                  \n");
 printf("    权 从 小 到 大 排 序 之 后 为：\n");
     printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");
     printf("   起始城市      终点城市      权\n");
 for (i = 1; i <= G->arcnum; i++)
 {   
          
     printf("      %d           %d            %d\n", edges[i].begin, edges[i].end, edges[i].weight);
 }

}

   
   void Swapn(edge *edges,int i, int j)     
{  
 
 int temp;   
  
 temp = edges[i].begin;  
    edges[i].begin = edges[j].begin;
    edges[j].begin = temp;
    temp = edges[i].end;  
    edges[i].end = edges[j].end;
    edges[j].end = temp;
    temp = edges[i].weight;  
    edges[i].weight = edges[j].weight;
    edges[j].weight = temp;
} 

    
   void MiniSpanTree(MGraph *G)
{
 int i, j, n, m;
 int k = 1;
    int parent[M];

 edge edges[M];
 
 for ( i = 1; i < G->vexnum; i++)
 {
  for (j = i + 1; j <= G->vexnum; j++)
  {
   if (G->arc[i][j].adj == 1)
   {
    edges[k].begin = i;
    edges[k].end = j;
    edges[k].weight = G->arc[i][j].weight;
       k++;
   }
   
  }
 }
        
    sort(edges, G);
    for (i = 1; i <= G->arcnum; i++)
 {
  parent[i] = 0;
 }
    printf("\n◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");
    printf("    最   小   生   成   树   为：\n");
	printf("==================================\n");
	printf("   起始城市      终点城市      权       \n");
 for (i = 1; i <= G->arcnum; i++)
 {
  n = Find(parent, edges[i].begin);
  m = Find(parent, edges[i].end);
  if (n != m)
  {
     parent[n] = m;
     printf("      %d           %d             %d\n", edges[i].begin, edges[i].end, edges[i].weight);
  }
  
 }
 printf("**********************************\n");
}

     
	int Find(int *parent, int f)
{
 while ( parent[f] > 0)
 {
  f = parent[f];
 }
    return f;
}

     
	int main(void)
{
 MGraph *G;
 G = (MGraph*)malloc(sizeof(MGraph));
 if (G == NULL)
 {
  printf("memory allcation failed,goodbye");
  exit(1);
 }

 CreatGraph(G);
    MiniSpanTree(G);
   
 system("pause");
 return 0;
}