若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网络，是一个网的最小生成树问题。本单元的实验内容主要是利用克鲁斯卡尔算法求出网的最小生成树，并且以文本形式输出树中的各条边以及他们的权值。

#include<iostream>
#include<stdlib.h>//产生随机数组用
#include<time.h> //同上
 #include<list>

 // 1) 带权边的类MyArc:

class MyArc
{
public:
    int m_beginVex;
    int m_endVex;
    int m_weight;
    MyArc(int beginVex,int endVex,int weight);
    MyArc(){}
    bool operator < (const MyArc& arc)
    {
        return m_weight<arc.m_weight;
    }
    bool operator == (const MyArc& arc)
    {
        return m_weight==arc.m_weight;
    }
    bool operator > (const MyArc& arc)
    {
        return m_weight>arc.m_weight;
    }
}  ;

MyArc::MyArc(int beginVex,int endVex,int weight):m_beginVex(beginVex),m_endVex(endVex),m_weight(weight)
{}
//2) 表示图的邻接矩阵类Graph:
class Graph
{
public:
    int m_vexnum;
    int m_arcnum;
    int *m_pmatrix;
public:
    ~Graph();
    Graph(int vexnum);
    Graph(int vexnum,int *pmatrix);
    void insert(MyArc arc);//按权值大小排序插入
    bool bound(int x);   //判断顶点x是否已与其它顶点连通
};
//构造函数
Graph::Graph(int vexnum)
{
    m_pmatrix=new int[vexnum*vexnum];
    m_vexnum=vexnum;m_arcnum=0;
    for(int i=0;i<vexnum*vexnum;++i)
    m_pmatrix[i]=0;

}

//构造函数
Graph::Graph(int vexnum,int *pmatrix)
{
    m_vexnum=vexnum;
    // m_arcnum=arcnum;
    m_pmatrix=new int[m_vexnum*m_vexnum];
    for(int i=0;i<m_vexnum*m_vexnum;++i)
        m_pmatrix[i]=pmatrix[i];
}

//测试 顶点x是否已与其他点连通
bool Graph::bound(int x)
{
    for(int i=0;i<m_vexnum;++i) if(m_pmatrix[x+i*m_vexnum]!=0) return true;
    return false;
}

//在邻接表中连通 arc表示的边，并且设置权
void Graph::insert(MyArc arc)
{
    m_pmatrix[arc.m_beginVex*m_vexnum+arc.m_endVex]=arc.m_weight;
    m_pmatrix[arc.m_endVex*m_vexnum+arc.m_beginVex]=arc.m_weight;
    ++m_arcnum;
}
//析构
Graph::~Graph()
{
    delete[] m_pmatrix;
}
//3) 按权存储边的有序队列类MyQueues:

//边按权值插入队列中合适位置,
class MyQueues
{
public:
    list<MyArc> m_list;
    MyQueues(){}
    void insert(const MyArc& arc);//边按权值插入队列中合适位置,
    void InsertGraph(const Graph &graph);//将图的连通分量插入队列
    MyArc pop();
};
//边出队
MyArc MyQueues::pop()
{
    MyArc arc=m_list.front();
    m_list.pop_front();
    return arc;
}
//边按权值插入队列中合适位置,
void MyQueues::insert(const MyArc& arc)
{
    list<MyArc>::iterator pos;
    pos=m_list.begin();
    while(pos!=m_list.end())
    {
        if(*pos>arc) break;
        else ++pos;
    }
    m_list.insert(pos,arc);
}
//将图的连通分量插入队列
void MyQueues::InsertGraph(const Graph &graph)
{
    for(int i=0;i<graph.m_vexnum;++i)
    {
        for(int j=i+1;j<graph.m_vexnum;++j)
              if(graph.m_pmatrix[i*graph.m_vexnum+j]) insert(MyArc(i,j,graph.m_pmatrix[i*graph.m_vexnum+j]));
    }
}

 //5)判断是否有回路的IsCycle函数：
bool IsCycle(Graph& graph, MyArc& arc)
{
    list<int> my_list;
    my_list.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(!my_list.empty())
    {
        int x=my_list.front();
        ps[x]=1;
        my_list.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) my_list.push_back(i);
              }
        }
    }
    delete[] ps;
    return false;
}
//4) kruskal算法:
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;
        }
    }
}