prim算法.cpp

用于数据结构课程设计,双向链表,并且用了MFC做图形界面

#include <iostream.h>

#define INFINITY INT_MAX                  //最大值：无穷大
#define MAX_VERTEX_NUM 20                 //最大顶点个数
#define MAX   100000                      //最大值

typedef float VRType;                      //顶点关系类型
typedef char VerTexType;                   //顶点类型 

typedef struct
{VRType adj;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //带权图的权值类型

typedef struct
{char vexs[MAX_VERTEX_NUM];        //顶点向量
 AdjMatrix arcs;                   //邻接矩阵
 int vexnum;                       //顶点数
}MGraph;                           //图的种类标志

typedef struct
{
 char adjvex;                        //记录生成树顶点集合外各顶点距离集合内哪个顶点最近
 VRType lowcost;                     //存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值
}closedge[MAX_VERTEX_NUM];          //最小生成树的辅助数组


void CreateGraph(MGraph &G);            //建立一个图G的邻接矩阵
void MiniSpanTree_PRIM(MGraph G, char u);    //用PRIM算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
                                             //记录从顶点集U到V-U的代价最小的边的辅助数组定义
int LocateVex(MGraph G, char u);   //确定顶点在图G中的位置
int minimum(closedge close);       //求出当前最小的边所依附的集合V-U中的顶点的位置

void main( void )       
{
 int i, j;
 MGraph G;
 
 CreateGraph(G);                      //建立图G的邻接矩阵
 for(i=0; i<G.vexnum; i++)            //输出图G的邻接矩阵
 {
  for(j=0; j<G.vexnum; j++)
  {
   cout<<G.arcs[i][j].adj;            //输出图G中各条边的权值
   cout<<"	";
  }
  cout<<endl;
 }
 MiniSpanTree_PRIM(G, 'a');            //建立最小生成树
 cin>>i; 
}


void CreateGraph(MGraph &G)
{
 float weigh;                  //定义权值类型 
 int i,j;
 int count=0;              //设立一个计数器，记录当前输入的边数
 char v1,v2;               //定义顶点类型
 
cout<<"请输入办公室个数："<<endl;
cin>>G.vexnum;                  //输入顶点数

cout<<"现在请输入所有这些办公室的房间号（以字母a-z表示）:";

  for(i=0; i<G.vexnum; i++)          //输入所有顶点
   cin>>G.vexs[i];
 cout<<endl;
 for(i=0;i<G.vexnum;i++)             //初始化各条边上的权值为最大值
   for(j=0;j<G.vexnum;j++)
   G.arcs[i][j].adj=MAX;
	 do                                //构造邻接矩阵
	 { cout<<"请分别输入两个办公室的房间号&在这两个办公室间布线需要的成本:"<<endl;
		cout<<"提示：为了建成局域网，您至少需要"<<G.vexnum-1<<"根接线，请至少输入"<<G.vexnum-1<<"组房间号码"<<endl;

    cout<<"请先输入第一个办公室的房间号，以字母表示（a-z）（如果您已经输入完毕所有房间请按#号键确认）:"<<endl;
  cin>>v1;                                                   //输入一条边依附的顶点
  cout<<endl<<"请再输入第二个办公室的房间号，以字母表示（a-z）（如果您已经输入完毕所有房间请按#号键确认）:"<<endl;
  cin>>v2;                                                   //输入该条边依附的另一个顶点
  cout<<endl<<"现在请输入这两个办公室间布线需要的成本（如果您已经输入完毕所有房间请按0确认）:";
  cin>>weigh;                                                 //输入这条边上的权值
  cout<<endl;
   i=LocateVex(G,v1);                                      //确定V1和V2在G中的位置
   j=LocateVex(G,v2);
   
  G.arcs[i][j].adj = weigh;                            //边<v1,v2>的权值
  G.arcs[j][i].adj = weigh;                           //置<v1,v2>的对称边<v2,v1>
  if(weigh!=0&&v1==G.vexs[i]&&v2==G.vexs[j])           //输入完一组顶点，统计一次当前图G的边数
  cout<<endl<<"您已经输入了"<<++count<<"组房间号码"<<endl<<endl;
 
  else cout<<"您一共输入了"<<count<<"组房间号码"<<endl;   //若输入已经进行完毕，统计图G的总边数
	 }
  while(v1!='#'||v2!='#'||weigh!=0);                  //若输入为进行完毕，返回DO语句，继续输入下一组顶点及权值
 
}

void MiniSpanTree_PRIM(MGraph G,char u)       //构造并显示最小生成树的PRIM算法
{
 int i,j,k= 0;
 closedge close;
 
 k = LocateVex ( G, u );                   //确定第一个输入的顶点在图G中的位置，并从该顶点出发开始建立最小生成树T
 for (j=0; j<G.vexnum; j++ )               //辅助数组close初始化
 {
  if (j!=k)                               
  {
   close[j].adjvex = G.vexs[k];            
   close[j].lowcost = G.arcs[k][j].adj;    
  }
 }
  close[j].lowcost = MAX;                  //若j对应的顶点与第一个输入的顶点间没有边，则令该边上的权值为最大值           
  close[j].adjvex = '\0';                  //同时，令j对应的顶点所依附的顶点为\0
  close[k].lowcost = 0;                   //初始，U={u}
  close[k].adjvex = u;
  cout<<"成本最低的接线为:"<<endl;          //输出成本最低的接线
 for (i = 1; i < G.vexnum; i++)              //选择其余G.vexnum-1个顶点
 { 
  k = minimum(close);                     //求出T的下一个结点：第K顶点

 
  cout<<close[k].adjvex;              //输出生成树的边
  cout<<"---->";
  cout<<G.vexs[k]<<" ";
  cout<<close[k].lowcost<<endl;
  close[k].lowcost = 0;               //第K顶点并入U集
  for (j=0; j<G.vexnum; j++)
  {
   if (G.arcs[k][j].adj < close[j].lowcost)           //新顶点并入U后重新选择最小边
   {
    close[j].adjvex = G.vexs[k];
    close[j].lowcost = G.arcs[k][j].adj;
   }
  }
 }
}

int LocateVex(MGraph G, char u)                    //确定输入的顶点在G中的位置
{ int i;
  for(i=0;i<G.vexnum;i++)
  {if(u==G.vexs[i])return i;}         //输入的顶点u存在于图G中
  if(i==G.vexnum&&u!='#')             //输入的顶点u不存在于图G中，并且输入还没有结束
  {cout<<"您输入的房间号码有错！请重新输入："<<endl;   //显示出错，并继续输入下一顶点
  return -1;}
  else {cout<<"您已经输入完毕!";       //输入完毕
	 return -1;}
  }
 



int minimum(closedge close)       //求当前最小边在顶点集V-U中所依附的顶点位置
{
 int i=0, client = MAX, j;
 while(close[i].adjvex != '\0')         //该顶点仍在V-U中
 {
  if (client > close[i].lowcost && close[i].lowcost != 0)   
  {client = close[i].lowcost;           //修改最小权值
  j = i; }                              //修改最小边在顶点集V-U中所依附的顶点位置
    i++;}
  return j;
}