若要在n個(gè)城市之間建設(shè)通訊網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通訊網(wǎng)絡(luò)，是一個(gè)網(wǎng)的最小生成樹問題。本單元的實(shí)驗(yàn)內(nèi)容主要是利用克魯斯卡爾算法求出網(wǎng)的最小生成樹，并且以文本形式輸出樹中的各條邊以及他們的權(quán)值。

#include<iostream>
#include<stdlib.h>//產(chǎn)生隨機(jī)數(shù)組用
#include<time.h> //同上
?#include<list>

?// 1) 帶權(quán)邊的類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);//按權(quán)值大小排序插入
??? bool bound(int x);?? //判斷頂點(diǎn)x是否已與其它頂點(diǎn)連通
};
//構(gòu)造函數(shù)
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;

}

//構(gòu)造函數(shù)
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];
}

//測(cè)試 頂點(diǎn)x是否已與其他點(diǎn)連通
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表示的邊，并且設(shè)置權(quán)
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;
}
//析構(gòu)
Graph::~Graph()
{
??? delete[] m_pmatrix;
}
//3) 按權(quán)存儲(chǔ)邊的有序隊(duì)列類MyQueues:

//邊按權(quán)值插入隊(duì)列中合適位置,
class MyQueues
{
public:
??? list<MyArc> m_list;
??? MyQueues(){}
??? void insert(const MyArc& arc);//邊按權(quán)值插入隊(duì)列中合適位置,
??? void InsertGraph(const Graph &graph);//將圖的連通分量插入隊(duì)列
??? MyArc pop();
};
//邊出隊(duì)
MyArc MyQueues::pop()
{
??? MyArc arc=m_list.front();
??? m_list.pop_front();
??? return arc;
}
//邊按權(quán)值插入隊(duì)列中合適位置,
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);
}
//將圖的連通分量插入隊(duì)列
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函數(shù)：
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; //邊的個(gè)數(shù)
??? while(arcnum<graph.m_vexnum-1)
??? {
??????? myarc=arcqueues.pop();
??????? if(!IsCycle(smtree,myarc))
??????? {
????????????? smtree.insert(myarc);
????????????? ++arcnum;
??????? }
??? }
}