C++ Prim算法Kruskal算法构造可以使n个城市连接的最小生成树

Green

　　1、 设计目的和要求（1）、实验题目：给定一个地区的n 个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并得到的最小生成树的代价。（2）、实验要求：  1、城市间的距离网采用的邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。  2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）  3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。2、 设计内容及步骤（1）、问题分析及采用数据结构：1、根据题目要求，首先要建立城市间的距离网，并且采用邻接矩阵表示，则使用到的数据结构是图的形式。图的作用是实现城市的距离网，采用顺序存储结构。数据结构可以用如下表示：

•  
  

typedef struct{  SeqList Vertices;  //存放图中各结点  int edge[MaxVertices][MaxVertices]; //存放权值的二维数组  int num_edge;     //图的边数}Graph;

2、完成距离网的存储后，就要用Prim算法和Kruskal算法来实验最小生成树。Prim算法是以结点为最小生成树的开始，再找其相应的最小边来实现。可以设计为两个参数，一个参数为图G，另一个参数是通过函数得到的最小生成树结点数据和相应结点的边的权值数据closeVertex.所以其数据结构可以定义如下：

•  
  

typedef struct{  DataType vertex;  int weight;}TreeNode;

Kruskal算法是以图中最小边开始慢慢寻找最小生成树的代价。所以它的结构包含最小边及边的两结点的下标，标置位是判断结点是否已经参加比较。其结构可以定义如下：

•  
  

typedef struct{  int row;   //行下标  int col;  //列下标  int weight;  //边权值  int flag;    //标志位}TreeEdge;//边信息

（2）算法设计1、首先设计的是顺序表，用来存放图中的各个结点的信息。这样可以看到结点的多少，又可以知道每个结点对应的下标，便于操作。 2、图的操作：图的操作主要体现在要实现城市的距离网的信息，所以其操作有：初始化，插入结点、插入边。A、 初始化GraphInitiate(G,n);初始化图G，n个结点个数。B、 插入结点InsertVertex(G,vertex)；在图中插入结点vertex.C、 插入结点InsertEdge(G,v1,v2,weight)；在图中插入边<v1,v2>,边<v1,v2>的权值为weight.3、prim算法的设计:Prim算法的函数设计为void Prim(Graph G);A、 函数中首先定义一个数组lowCost，数组过犹不及lowCost[v]中保存了集合U中结点u(i)与集合VU中结点v(j)的所有边中当前具有最小权值的边<u,v>.B、 集合U的初值为U={序号为0的结点}。lowCost的初始值为邻接矩阵数组中第0行的值，这样初始时lowCost中就存放了从集合U中结点0到集合VU中各个结点的权值。C、 每次从lowCost中寻找具有最小权值的边，根据lowCost的定义，这样的边其弧头结点必然为集合U中的结点，其弧尾结点必然为集合VU中的结点为。当选到一条这样的边(u,v)时，就保存其结点数据和权值的数据到参数closeVertex中，并将lowCost[v]置-1。D、 当结点v从集合VU加入到集合U后，若存在一条边<u,v>，u是集合U的结点，v是集合VU的结点，且边<u,v>较原先lowCost[v]的权值更小，则用这样的权值修改原先lowCost[v]中的相应权值。3、Kruskal算法的设计:Kruskal算法函数设计为void Kruskal(Graph G).A、 首先将所有有权值（MaxSize>weight>0）的边存放到lowCost数组里。并且标置位flag置0。B、 根据lowCost存放所有的结点来寻找最小的权值。若找到刚先保存起来，标置位为1。并要判断是否符合。C、 将B中找到的边的两个结点的下表与顺序表中的数据比较，如果没有则进表保存，如果两个都有则说明此边会与前面找到的最小边构成了回路，不符合。D、 重复B，C操作。三、源程序代码块：首先要建立顺序表其函数包含在头文件：SeqList.h中

•  
  

#define MaxSize 20typedef struct{  DataType list[MaxSize];  int size;}SeqList;void ListInitiate(SeqList *L) //初始化{  L->size=0;}int ListLength(SeqList L) //表长{  return L.size;}//插入int ListInsert(SeqList *L,int i,DataType x){  int j;  if(i<0||i>MaxSize)  {    printf("插入参数不合法!");    return 0;  }  else  {    for(j=L->size;j>i;j--)      L->list[j]=L->list[j-1];    L->list[i]=x;    L->size++;    return 1;  }}//删除int ListDelete(SeqList *L,int i,DataType *x){  int j;  if(i<0||i>MaxSize)  {    printf("插入参数不合法!");    return 0;  }  else  {    *x=L->list[i];    for(j=i;j<L->size;j++)      L->list[j]=L->list[j+1];    L->size--;    return 1;  }}void ListGet(SeqList *L,int i,DataType *x) //取元素{  *x=L->list[i];}int Search(SeqList *L,DataType x,int *i) //找结点的下标{  int j;  for(j=0;j<L->size;j++)  {    if(x==L->list[j])    {      *i=j;      return 1;    }  }  printf("无该结点");  return 0;}int IsIn(SeqList L,DataType x)//判断L中是否有x,有返回1,无返回0{  int i;  for(i=0;i<L.size;i++)  {    if(x==L.list[i])      return 1;  }  return 0;}

图的头文件：vertex.h

•  
  

#include "SeqList.h"#define MaxWeight 10000typedef struct{  SeqList Vertices;  //存放图中各结点  int edge[MaxVertices][MaxVertices]; //存放权值的二维数组  int num_edge;     //图的边数}Graph;//初始化void GraphInitiate(Graph *G,int n){  int i,j;  for(i=0;i<n;i++)    for(j=0;j<n;j++)    {      if(i==j) G->edge[i][j]=0;  //二维数组的对角权值为0      else        G->edge[i][j]=MaxWeight;//二维数组各权值初始为无穷    }  G->num_edge=0;  ListInitiate(&G->Vertices);}//插入结点void VertexInsert(Graph *G,DataType vertex){  ListInsert(&G->Vertices,G->Vertices.size,vertex);}//插入图结点间的权值void EdgeInsert(Graph *G,DataType x1,DataType x2,int weight){  int v1,v2;  Search(&G->Vertices,x1,&v1);  Search(&G->Vertices,x2,&v2);  G->edge[v1][v2]=weight;  G->edge[v2][v1]=weight;  G->num_edge++;}

Prim算法的实现：prim.h

•  
  

typedef struct{  DataType vertex;  int weight;}TreeNode;void prim(Graph G){  DataType x;  int m=0,n=G.Vertices.size,minCost;  TreeNode *closevertex;  int *lowCost=(int *)malloc(sizeof(int)*n);  int i,j,k;  closevertex=(TreeNode *)malloc(sizeof(TreeNode)*n);  for(i=1;i<n;i++)    lowCost[i]=G.edge[0][i];ListGet(&G.Vertices,0,&x);  closevertex[0].vertex=x;  lowCost[0]=-1;  for(i=1;i<n;i++)  {    minCost=MaxWeight;    for(j=1;j<n;j++)    {      if(lowCost[j]<minCost&&lowCost[j]>0)      {        minCost=lowCost[j];        k=j;      }    }ListGet(&G.Vertices,k,&x);    closevertex[i].vertex=x;    closevertex[i].weight=minCost;    lowCost[k]=-1;    for(j=1;j<n;j++)    {      if(G.edge[k][j]<lowCost[j])        lowCost[j]=G.edge[k][j];    }  }  printf("初始结点=%c ",closevertex[0].vertex);  for(i=1;i<n;i++)  {    printf("结点=%c 边的权值=%d ",closevertex[i].vertex,closevertex[i].weight);    m=m+closevertex[i].weight;  }  printf("代价和为:%d",m);}

Kruskal算法的实现:kruskal.h

•  
  

typedef struct{  int row;   //行下标  int col;  //列下标  int weight;  //边权值  int flag;    //标志位}TreeEdge;//边信息void kruskal(Graph *G){  typedef int DataType;  int daijia=0;  int n=G->num_edge;  int minCost;TreeEdge treeedge[20];  TreeEdge *lowCost=(TreeEdge *)malloc(sizeof(TreeEdge)*n);  int i,j,k,m;  SeqList L;  ListInitiate(&L);  i=0; //将所有边的信息都存入到lowCost里边  while(i<n)        {    for(j=0;j<G->Vertices.size;j++)      for(k=j;k<G->Vertices.size;k++)//存放有权值的结点      {        if(G->edge[j][k]>0&&G->edge[j][k]<MaxWeight)        {          lowCost[i].weight=G->edge[j][k];          lowCost[i].row=j;          lowCost[i].col=k;          lowCost[i].flag=0; //标志位          i++;        }                                }  }  m=0;  while(m<G->Vertices.size-1)  {    //找最小的权值    minCost=MaxWeight;    for(j=0;j<n;j++)    {      if(lowCost[j].weight<minCost&&lowCost[j].flag==0)      {        minCost=lowCost[j].weight;        k=j;      }    }    lowCost[k].flag=1;//判断找到的边是否构成图    if(!(IsIn(L,lowCost[k].row)&&IsIn(L,lowCost[k].col)))    {      if(!IsIn(L,lowCost[k].row))        ListInsert(&L,L.size,lowCost[k].row);      if(!IsIn(L,lowCost[k].col))        ListInsert(&L,L.size,lowCost[k].col);      treeedge[m]=lowCost[k];      m++;    }  }//输出结果  for(i=0;i<m;i++)  {printf("权值=%d  两城市=%c  %c ",treeedge[i].weight,G->Vertices.list[treeedge[i].row],G->Vertices.list[treeedge[i].col]);    daijia+=treeedge[i].weight;  }  printf("代价和为：%d",daijia);}

测试函数。Test.cpp

•  
  

#include <stdio.h>#include <stdlib.h>typedef char DataType;#define MaxVertices 20#include "Vertex.h"#include "prim.h"#define MaxNums 200#include<string.h>void f(Graph G){    //用prim算法得到的结果  printf("…………prim算法得到的结果为： ");  prim(G);}int main(){  Graph G;DataType c[100];  DataType c1[100];DataType c2[100];  int number;//  int n,m,i,j,q;      //读取文件FILE *fp ;   int i1,j1;   int nums=0;   DataType words[100][21]; //最多读100个单词，每个单词不超过20个字符   fp=fopen("data.txt", "r");   if ( fp==NULL )   {     printf("open file error ");     return -1;   }   for( i1=0;i1<100;i1++ ) //循环读取，控制不超过100个   {     if ( fscanf(fp, "%20s", words[i1] )!= 1 ) //控制每个单词不超过20个       break;   }   fclose(fp);   for( j1=0;j1<i1;j1++ ) //反向输出各单词   {//    printf( "%s ", words[j1] ) ;     nums++;  }//  printf(" ");//  printf("%d",nums);//  printf(" ");//  printf( "%s ", words[1] ) ;    //读取文件//  printf("请输入城市个数:");//  scanf("%d",&n);  printf("下面是从文件读取到的数据：");  printf(" ");  int n = (atoi(words[0]));  number = n;  printf("城市个数:%d",n);  printf(" ");  GraphInitiate(&G,n);//  printf("请依次输入城市名（输完一个按回车继续输入）: ");  for(int i=0;i<n;i++)  {    c[i] = *words[i+1];//    测试输出    printf( "城市名称：%s ", words[i+1] ) ;    printf(" ");//    scanf("%s",&c[i]);    VertexInsert(&G,c[i]);  }//  printf("请输入要输入的边数:");  int m = (atoi(words[n+1]));  //    测试输出  printf( "边数：%s ", words[n+1] ) ;  printf(" ");//  scanf("%d",&m);//  printf("请输入两城市的权值: ");  for(int j=0;j<m;j++)  {//    scanf("%s",&c1[j]);  c1[j] = *words[number+2+3*j];  //    测试输出//    scanf("%s",&c2[j]);    c2[j] = *words[number+3+3*j];//    printf("输入权值:");//    scanf("%d",&q);    int q = (atoi(words[number+4+3*j]));    EdgeInsert(&G,c1[j],c2[j],q);    EdgeInsert(&G,c1[j],c2[j],q);  }  printf(" ");  printf("矩阵：");  printf(" ");  for(int i=0;i<G.Vertices.size;i++)  {    for(int j=0;j<G.Vertices.size;j++)      printf("%7d",G.edge[i][j]);    printf(" ");    }  printf(" ");  f(G);  return 0;}

程序运行结果：

•  
  

请输入城市个数：7请依次输入城市名：a b c d e f g请输入要输入的边数：10请输入两城市的权值：输入城市：a  与它相连的城市b  它们的权值：50输入城市：a  与它相连的城市c  它们的权值：60输入城市：b  与它相连的城市d  它们的权值：65输入城市：b  与它相连的城市e  它们的权值：40输入城市：c  与它相连的城市d  它们的权值: 52输入城市：c  与它相连的城市g  它们的权值：45输入城市：d  与它相连的城市e  它们的权值：50输入城市：d  与它相连的城市f  它们的权值：30输入城市：d  与它相连的城市g  它们的权值：42输入城市：e  与它相连的城市f  它们的权值：70   0    50    60   10000   10000   10000   10000  50     0   10000    65    40   10000   10000  60   10000     0    52   10000   10000    45           10000    65    52     0    50    30    42           10000    40   10000    50     0    70   10000           10000   10000   10000    30    70     0   10000           10000   10000    45    42   10000  10000    0…………prim算法得到的结果为：初始结点=a结点=b 边的权值=50结点=e 边的权值=40结点=d 边的权值=50结点=f 边的权值=30结点=f 边的权值=42结点=c 边的权值=45代价和为:257  ……………………kruskal算法得到的结果为：权值=30  两城市=d  f权值=40  两城市=b  e权值=42  两城市=d  g权值=45  两城市=c  g权值=50  两城市=a  b权值=50  两城市=d  e代价和为:257…………

附：增加模块：在原来距离网的基础上重新再加一个节点并重新设计最小生成树。（1） 首先先把原来的图中信息保存，再重新初始化一个n+1个结点的图。（2） 再插入新的结点及与其相关的权值信息。

•  
  

void Insert(Graph *g){  DataType m,n;  int k;  int i,j;  char c='y',c1;  printf("请输入要插入的结点:");  scanf("%s",&m);  VertexInsert(g,m);  while(c=='y'||c=='Y')  {    printf("请输入它与哪个结点相连：");    scanf("%s",&n);    printf("请输入它们的权值：");    scanf("%d",&k);    EdgeInsert(g,m,n,k);    printf("它是否还有其它相连的结点（y/n):");    scanf("%s",&c1);    c=c1;  }  for(i=0;i<g->Vertices.size;i++)  {    for(j=0;j<g->Vertices.size;j++)      printf("%7d",g->edge[i][j]);    printf(" ");    }//写代码很累，多加关注科技毒瘤君}