資料結構-最小生成樹

最小生成樹

• 說明：本人還是初學者，以下給出的代碼是教材資料結構C語言版第二版（嚴蔚敏 李冬梅 吳偉民 編著）中關于最小生成樹Kruskal算法代碼段的整合，本人用于簡單的城市間道路網課程設計，僅供參考。
• 完整代碼：

#include <iostream>
using namespace std;

#include <fstream>

#define MaxInt 32767                                                    //表示極大值，即 ∞
#define MVNum 100                                                       //最大頂點數
#define OK 1

typedef char VerTexType;                                               //假設頂點的資料類型為字元型 
typedef int ArcType;                                                   //假設邊的權值類型為整形 

ifstream infile;                                                       //定義輸入檔案流對象 

typedef struct
{//圖的鄰接矩陣存儲表示 
	VerTexType vexs[MVNum];                                            //頂點表 
	ArcType arcs[MVNum][MVNum];                                        //鄰接矩陣 
	int vexnum, arcnum;                                                //圖的目前點數和邊數 
}AMGraph;
AMGraph G;

typedef struct Edge
{ 
	VerTexType Head;                                                   //邊的始點
	VerTexType Tail;                                                   //邊的終點
	ArcType lowcost;                                                   //邊上的權值
};
Edge Edges[MVNum];                                                     //輔助數組Edges和E的定義 
Edge E;

int Vexset[MVNum];                                                     //輔助數組Vexset存放 

int LocateVex(AMGraph G, char u)
{//傳回頂點u在圖G中的位置
	int   i;
	for (i = 0; i<G.vexnum; ++i)                                       //輸入的頂點u與頂點表中的頂點依次比較 
		if (u-G.vexs[i]=='\0')
			return   i;
	return   OK;
}

int CreateUDN(AMGraph &G)
{//采用鄰接矩陣表示法，建立無向圖G 
	infile>> G.vexnum >> G.arcnum;                                    //輸入總頂點數，總邊數
	for (int i = 0; i<G.vexnum; i++) {                                //依次輸入點的資訊 
		infile>> G.vexs[i];
	}
	for (int i = 0; i<G.vexnum; i++) {                                //初始化鄰接矩陣，邊的權值均置為極大值MaxInt
		for (int j = 0; j<G.vexnum; ++j) {
			G.arcs[i][j] = MaxInt;
		}
	}
	for (int k = 0; k<G.arcnum; ++k) {
		char v1, v2;
		int i, j, w;
		infile >> v1 >> v2 >> w;                                      //輸入一條邊依附的頂點和權值
		i = LocateVex(G, v1); j = LocateVex(G, v2);                   //确定v1和v2在G中的位置，即頂點數組的下标
		G.arcs[i][j] = w;                                             //邊<v1,v2>的權值置為w
		G.arcs[j][i] = G.arcs[i][j];                                  //置<v1,v2>的對稱邊<v2,v1>的權值為w	 
	}
	return OK;
}

int Sort(Edge Edges[])
{//将數組Edge中的元素按權值從小到大排序
	int i,j,k=0;
	for (i = 0; i<G.vexnum; i++) {                                    //邊集數組初始化,隻考慮上三角矩陣  
		for (j = i; j<G.vexnum; j++) {
			if (G.arcs[i][j]!=MaxInt) {
				Edges[k].Head = G.vexs[i];
				Edges[k].Tail = G.vexs[j];
				Edges[k].lowcost = G.arcs[i][j];
				k++;				
			}
		}
	}
	for (i = 0; i<G.arcnum-1; i++) {                                  //對邊集數組進行選擇排序  
		for (j = i + 1; j<G.arcnum; j++) {
			if (Edges[i].lowcost > Edges[j].lowcost) {
				E = Edges[i];
				Edges[i] = Edges[j];
				Edges[j] = E;
			}
		} 
	}
}

void MiniSpanTree_Kruskal(AMGraph G)
{//無向網G以鄰接矩陣形式存儲，構造G的最小生成樹T，輸出T的各條邊
	int v1, v2, vs1, vs2;
	int min=0;
	Sort(Edges);                                                      //将數組Edge中的元素按權值從小到大排序
	for (int i = 0; i<G.vexnum; i++)                                  //輔助數組，表示各頂點自成一個連通分量
		Vexset[i] = i;
	cout<<"最小生成樹中包括的城市間的道路有："<<endl;
	for (int i = 0; i<G.arcnum; i++) {                                //依次檢視數組Edge中的邊
	
		v1 = LocateVex(G, Edges[i].Head);                             //v1為邊的始點Head的下标
		v2 = LocateVex(G, Edges[i].Tail);                             //v2為邊的終點Tail的下标
		vs1 = Vexset[v1];                                             //擷取Edge[i]的始點所在的連通分量vs1
		vs2 = Vexset[v2];                                             //擷取Edge[i]的終點所在的連通分量vs2
		if (vs1 != vs2) {                                             //邊的兩個頂點分屬不同的連通分量
			cout <<"邊："<<Edges[i].Head <<"--"<< Edges[i].Tail
			<<"，權值："<<Edges[i].lowcost<<endl;                       //輸出此邊和權值 
			min=min+Edges[i].lowcost;                                 //累加計算最小生成樹的代價
			for (int j = 0; j<G.vexnum; j++)                          //合并vs1和vs2兩個分量，即兩個集合統一編号
				if (Vexset[j] == vs2)  Vexset[j] = vs1;               //集合編号為vs2的都改為vs1 
		}
	}
	cout<<"最小生成樹的代價為："<<min<<endl;
}

int sc()
{
cout<<"輸出城市間距離網的鄰接矩陣："<<endl;
	for (int i = 0; i<G.vexnum; i++) {
		for (int j = 0; j<G.vexnum; j++) {
			if (G.arcs[i][j] == MaxInt)                               //将MaxInt的數值替換為字元 ∞
				cout<<"∞"<<" ";
			else
				cout<<G.arcs[i][j]<<"  ";
		}
		cout<<endl;
	}
	return OK;
}

int main()
{
	infile.open("1.txt",ios::in);
	if(!infile) {
		cerr<<"檔案打開失敗！"<<endl;
		exit(1); 
	}
	CreateUDN(G);
	sc();
	MiniSpanTree_Kruskal(G);
}
           

檔案格式示例：

結果如下：