董丽.cpp

给定一个地区的n个城市间的距离网

// 董丽.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <malloc.h>
using namespace std; 
#define int_max 0
#define inf 9999 
#define max 20
//…………………………………………邻接矩阵定义……………………
typedef struct ArcCell
{
 int adj;
 char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct 
{
 char vexs[20];
 AdjMatrix arcs;
 int vexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
 int i=0;
 while(G.vexs[i]!=v)
 {
  ++i;
 }
 return i;
}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{
 char v1,v2;
 int i,j,w;
 cout<<endl;
 cout<<endl<<endl;
 cout<<"★★★★★★★★★★★★★你好!欢迎进入最小生成树★★★★★★★★★★★★★★★"<<endl<<endl<<endl;
 cout<<"            ◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎                "<<endl<<endl;
 cout<<"----------------------------创建城市分布图(无向图)------------------------------"<<endl;
 cout<<endl;
 cout<<endl;
 cout<<endl<<"请输入城市和道路的个数(注：中间用空格连接):";
 cin>>G.vexnum>>G.arcnum;
 for(i=0;i!=G.vexnum;++i)
 {
  cout<<endl;
  cout<<"输入城市名称----"<<i<<endl;
  cin>>G.vexs[i];
 }
 for(i=0;i!=G.vexnum;++i)
  for(j=0;j!=G.vexnum;++j)
  { 
   G.arcs[i][j].adj=int_max;
   G.arcs[i][j].info=NULL;
  }
 for(int k=0;k!=G.arcnum;++k)
  { 
   cout<<"输入一条道路连接的城市名称和长度(注：中间用空格连接):"<<endl;
   cin>>v1>>v2>>w;//输入一条边依附的两点及权值
   i=localvex(G,v1);//确定顶点V1和V2在图中的位置
   j=localvex(G,v2);
   G.arcs[i][j].adj=w;
   G.arcs[j][i].adj=w;
  }
  system("cls");
  return G.vexnum;
}
void ljjzprint(MGraph_L G)
{
 int i,j;
 for(i=0;i!=G.vexnum;++i)
  {cout<<"                      ";
   for(j=0;j!=G.vexnum;++j)
   printf("%-8d",G.arcs[i][j].adj);
   cout<<endl;
   cout<<endl;
   cout<<endl;
  }
}
int visited[max];//访问标记
int we;
typedef struct arcnode//弧结点
{
 int adjvex;//该弧指向的顶点的位置
 struct arcnode *nextarc;//弧尾相同的下一条弧
 char *info;//该弧信息
}arcnode;
typedef struct vnode//邻接链表顶点头接点
{
 char data;//结点信息
 arcnode *firstarc;//指向第一条依附该结点的弧的指针
}vnode,adjlist;
    typedef struct//图的定义
{
 adjlist vertices[max];
 int vexnum,arcnum;
 int kind;
}algraph;

int prim(int g[][max],int n) //最小生成树PRIM算法
{
 int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
         //prevex[]存储最短路径在U中的结点
 int i,j,k,min;
 int sum=0; 
 for(i=2;i<=n;i++) //n个顶点，n-1条边 
 {
  lowcost[i]=g[1][i]; //初始化 
  prevex[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; 
   } 
   cout<<endl;
   cout<<endl;
  printf("                         边：(%d,%d)    代价：%d\t",prevex[k]-1,k-1,min); 
  sum+=min;
  lowcost[k]=0; //顶点k加入U 
  for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值 
   if(g[k][j]<lowcost[j]) 
   {
    lowcost[j]=g[k][j]; 
    prevex[j]=k; 
   } 
  printf("\n"); 
 }  
cout<<endl;
cout<<endl;
cout<<endl;
cout<<"                          最小生成树的代价:";
cout<<sum;
cout<<endl;
cout<<endl;
cout<<endl;
return 0;
} 
void main()
{ 
 system("color 0f");
 MGraph_L G;
 int i,d,g[20][20];
 char a='a';
 d=creatMGraph_L(G);

 int s;
 char y='y';
 while(y='y')
 {
  cout<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"…………………………………………………功能菜单……………………………………………"<<endl<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"1、显示该城市连接图的邻接矩阵……………………"<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"2、最小生成树的边与权值和代价……………………"<<endl;
  cout<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"请选择菜单项："<<endl;
  cin>>s;
  system("cls");
  switch(s)
  {
  case 1:
   cout<<endl;
   cout<<"                        城市连接图的邻接矩阵显示如下："<<endl;
   cout<<endl;
   cout<<endl;
   cout<<endl;
   cout<<endl;
   ljjzprint(G);
   break;
  case 2:
   for(i=0;i!=G.vexnum;++i)
    for(int j=0;j!=G.vexnum;++j)
     g[i+1][j+1]=G.arcs[i][j].adj;
   cout<<endl;
   cout<<"                       最小生成树的边与权值和代价："<<endl;
   cout<<endl;
   cout<<endl;
   prim(g,d);
   break;
  }
  cout<<endl<<"                     是否继续？y/n:";
   cin>>y;
  if(y=='n')
   break;
  system("cls");
 }

}