#include<iostream>
#include<stdlib.h>//產(chǎn)生隨機(jī)數(shù)組用
#include<time.h>  //同上
#include"base"  //所用到的自定義數(shù)據(jù)結(jié)構(gòu)定義和實(shí)現(xiàn)文件
using namespace std;

bool IsCycle(Graph& graph,MyArc& arc);         //判斷是否構(gòu)成回路
void kruskal(const Graph& graph,Graph& smtree);//克魯斯卡爾算法
void SmallestTreeOutput(const Graph& smtree);  //輸出最小生成樹  
void SetMatrix(int vexnum,int *matrix);        //用隨機(jī)數(shù)組初始化matrix數(shù)組并且打印
/*
主函數(shù)
*/
void main()
{
      char i;
      cout<<"請輸入頂點(diǎn)數(shù)目:";
      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;
}

//用隨機(jī)數(shù)組初始化matrix數(shù)組并且打印
void SetMatrix(int vexnum,int *pmatrix)
{       
      srand((unsigned)time(NULL));
      for(int i=0;i<vexnum;++i)//產(chǎn)生隨機(jī)權(quán)值矩陣
      {
             for(int j=i;j<vexnum;++j)
             {       
                    if(j==i)
                    {
                           pmatrix[i*vexnum+j]=0;
                           continue;
                    }
                    int rnum=rand();rnum%=99;rnum++;//產(chǎn)生1~99的隨機(jī)整數(shù)作為邊的權(quán)值
                    pmatrix[i*vexnum+j]=rnum;
                    pmatrix[j*vexnum+i]=rnum;
             }
      }
      cout<<"***隨機(jī)產(chǎn)生的各邊權(quán)值矩陣 [頂點(diǎn)數(shù)為 "<<vexnum<<"] ****\n";
   for(int i=0;i<vexnum;++i)//輸出隨機(jī)權(quán)值矩陣
      {
             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; //邊的個數(shù)
      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;
}