555.cpp

最小生成树 用克鲁斯卡尔算法求网的最小生成树

#include<iostream>
#include<stdlib.h>//产生随机数组用
#include<time.h>  //同上
#include"base"  //所用到的自定义数据结构定义和实现文件
using namespace std;

bool IsCycle(Graph& graph,MyArc& arc);         //判断是否构成回路
void kruskal(const Graph& graph,Graph& smtree);//克鲁斯卡尔算法
void SmallestTreeOutput(const Graph& smtree);  //输出最小生成树  
void SetMatrix(int vexnum,int *matrix);        //用随机数组初始化matrix数组并且打印
/*
主函数
*/
void main()
{
      char i;
      cout<<"请输入顶点数目:";
      cin>>i;
   int vex=i-'0';
      int *matrix=new int[vex*vex];
      cout<<endl;
      SetMatrix(vex,matrix);       
      Graph graph(vex,matrix),smtree(vex);
      kruskal(graph,smtree);
      SmallestTreeOutput(smtree);
      delete []matrix;
}

//用随机数组初始化matrix数组并且打印
void SetMatrix(int vexnum,int *pmatrix)
{       
      srand((unsigned)time(NULL));
      for(int i=0;i<vexnum;++i)//产生随机权值矩阵
      {
             for(int j=i;j<vexnum;++j)
             {       
                    if(j==i)
                    {
                           pmatrix[i*vexnum+j]=0;
                           continue;
                    }
                    int rnum=rand();rnum%=99;rnum++;//产生1~99的随机整数作为边的权值
                    pmatrix[i*vexnum+j]=rnum;
                    pmatrix[j*vexnum+i]=rnum;
             }
      }
      cout<<"***随机产生的各边权值矩阵 [顶点数为 "<<vexnum<<"] ****\n";
   for(int i=0;i<vexnum;++i)//输出随机权值矩阵
      {
             for(int j=0;j<vexnum;++j)
             {       
                    cout<<pmatrix[i*vexnum+j]<<"\t";
             }
             cout<<endl;
      }

}


//判断连通边arc后 图graph 是否存在回路   
bool IsCycle(Graph& graph, MyArc& arc)  
{
      list<int> mylist;
      mylist.push_back(arc.m_beginVex);
      int *ps=new int[graph.m_vexnum];
      for(int i=0;i<graph.m_vexnum;++i)
             ps[i]=0;
      while(!mylist.empty())
      {
             int x=mylist.front();
             ps[x]=1;
             mylist.pop_front();
             for(int i=0;i<graph.m_vexnum;++i)
             {
                    if(graph.m_pmatrix[i+x*graph.m_vexnum]!=0)
                    {
                           if(i==arc.m_endVex) return true;
                           if(ps[i]!=1) mylist.push_back(i);
                    }
             }
      }
      delete[] ps; 
      return false;
}

//克鲁斯卡尔算法
void kruskal(const Graph& graph,Graph& smtree)
{
      MyQueues  arcqueues;//保存从小到大排列的边
      arcqueues.InsertGraph(graph);
      MyArc myarc;//Arc表示边的类型
      int arcnum=0; //边的个数
      while(arcnum<graph.m_vexnum-1)
      {
             myarc=arcqueues.pop();
             if(!IsCycle(smtree,myarc))
             {
                    smtree.insert(myarc);
                    ++arcnum;
             }
      }
}

//输出最小生成树
void SmallestTreeOutput(const Graph& smtree)
{
      cout<<"最小生成树:"<<endl;
      for(int i=0;i<smtree.m_vexnum;++i)//输出最小树
             for(int j=i+1;j<smtree.m_vexnum;++j)
                    if(smtree.m_pmatrix[i*smtree.m_vexnum+j])
                           cout<<'('<<i<<','<<j<<','<<smtree.m_pmatrix[i*smtree.m_vexnum+j]<<')'<<endl;
}