最小生成木問題:n都市間に通信ネットワークを構築するには,n−1回線を架設するだけでよい(隣の学校の同級生の授業)

問題8最小生成木問題(難易度係数:1.1)[問題記述]n都市間に通信ネットワークを構築するには,n−1回線を架設するだけでよい.どのように最低の経済的代価でこの通信網を建設するかは、網の最小生成ツリーの問題である.[基本要求](1)クルーズカールアルゴリズムを用いてネットワークの最小生成ツリーを求める.(2)実装してセットを調べる.これにより、構築ツリー中の連通成分を表します.(3)生成ツリー内の各エッジおよびそれらの重み値をテキスト形式で出力する.[テストデータ]本題セットの練習問題を参照してください.[実装ヒント]通信回線が確立されると、必然的に双方向になる.したがって,最小生成ツリーを構築する網は必ず無方向網である.図の頂点数が30個を超えないように設定し、簡単にするために網中辺の重み値を100未満の整数に設定し、C言語で提供される乱数関数で生成することができる.図の記憶構造の選択は、操作に適応しなければならない.重み値が最も小さいエッジの選択を容易にするために,この問題の記憶構造は隣接行列の配列表現法も隣接テーブルも選択せず,記憶エッジ(重み付き)の配列で図を表す.[コンテンツを選択]スタックソートにより、選択権値が最も小さいエッジを実現します.

#pragma once
#ifndef EDGE
#define EDGE
//        
#define MaxNum 30//     
#define MaxInt 32767//   
#define MinInt -1//    
typedef char  VerType;//    
typedef int ArcType;//    
//      
typedef struct {
	VerType ver[MaxNum];//   
	ArcType arc[MaxNum][MaxNum];//    
	int vernum, arcnum;	//  ，  
}AMGraph;
//      1，Edge：      ，           
struct edge {
	VerType Head;//    
	VerType Tail;//    
	ArcType lowCost;//    
}Edge[MaxNum+1];//    
// n           n(n-1)  ,   n  ,         31， 1-30   
//  
int Locate(AMGraph G, VerType v1) {
	for (int i = 0; i < G.vernum; i++) {
		if (G.ver[i] == v1) {
			return i;
		}
	}
	return -1;
}
#endif

#pragma once
#ifndef HEAPSORT
#define HEAPSORT
#include
#include
#include"Edge.h"
//   -》   
using namespace std;
void show_heapSort_result(edge l[], int n) {
	for (int i = 1; i <=n; i++) {
		cout << l[i].lowCost << " ";
	}
	cout << endl;
}
// Heap Sort       ，r[n]               ，               ，            
//   ：1、Ki>=k（2i） &&Ki>=k(2i+1) 2、ki<=k(2i) &&Ki<=k(2i+1)
//1、      
//  ：1.r[2s] r[2s+1]         ，  r[2s+1] ，   r[s] r[2s]    
void heapAdjust(edge L[],int s,int m) {
	//  r[s+1,..m]  ， r[s,..m]    r[s]      
	edge rc = L[s];
	for (int j = 2 * s; j <= m; j *= 2) {// N/2、N/2-1……  ，                 
		if (j < m && L[j].lowCost < L[j + 1].lowCost ) ++j;//  .r[2s] r[2s+1]
		if (rc.lowCost >= L[j].lowCost) {
			break;
		}//    ，    
		else
			L[s] = L[j]; 
			s = j;//  r[2s] r[2s+1]   
	}
	L[s] = rc;
}
//2.  ，  r[s]
//			      ，    
//2.    ,         4n
//          n/2（    ）       ，   
//        ，    
void CreateHeap(edge L[],int length) {
	//      
	for (int i = length / 2; i > 0; --i) {
		heapAdjust(L,i ,length );
	}
}
//    
//            ,(n-1)   
void HeapSort(edge L[], int length) {
	CreateHeap(L, length);
	//int time = 1;
	for (int i = length; i > 1; --i) {
		edge x = L[1];
		L[1] = L[i]; 
		L[i] = x;
		heapAdjust(L, 1, i - 1);
		//printf(" %2d   \t", time++);
		//show_heapSort_result(L, length);
	}
}
//    
/*
     ：    O(nlog2n)
     o(1)
  ：   ；      ；        ，      ，   
*/
#endif

#include
#include"heapSort.h"
#include
using namespace std;
//     
/*
        ，      。
  ，               。
         30 ，      ，          100   ，   C            。
*/
bool createUDN(AMGraph &G) {
	cout << "Please input the vernum and arcnum(     )" << endl;//     
	cin >> G.vernum >> G.arcnum;
	cout << "Please input the name of "<<G.vernum<<" points" << endl;
	int i = 0, j = 0;
	for (i = 0; i < G.vernum; i++)
		cin >> G.ver[i];
	//       
	for (i = 0; i < G.vernum; i++) {
		for (j = 0; j < G.vernum; j++) {
			if (i != j)
				G.arc[i][j] = MaxInt;
			else 
				G.arc[i][j] = 0;
		}
	}
	//    ,     
	cout << "Please input the name of two arcnums and end with line feeds at a time,without inputing a random value as their distance"<< endl;
	VerType v1, v2;
	ArcType w;
	int p, q;
	srand((unsigned)time(NULL));
	for (i = 1; i <= G.arcnum; i++) {//       ，     
		cin >> v1 >> v2; //>> w;
		w = rand() % 100+1;// 1-100
		p = Locate(G, v1);
		q = Locate(G, v2);
		Edge[i] = { v1,v2,w };
		G.arc[p][q] = w;
		G.arc[q][p] = G.arc[p][q];
	}
	return true;
}
void show_Graph(AMGraph G) {
	int i, j;
	for (i = 0; i < G.vernum; i++) {
		for (j = 0; j < G.vernum; j++) {
			if (G.arc[i][j] == MaxInt)  printf("INF\t");
			else printf("%-3d\t", G.arc[i][j]);
		}
		cout << endl;
	}
}
//    ：   
//			1.   Edge         
//			2.        ，      ：
//				2.1       Edge        （u,u2)；
//				2.2 Vexset     v1,v2       vs1,vs2，    
//					  vs1==vs2,  2            ，    ，            
//					vs1!=vs2,  2             ，    ，        
//      2，Vexset[i]              ，               
//    
void MiniSpanTree_Kruskal(AMGraph G) {
	//            ，  G      ，  T   
	//   
	int Vexset[MaxNum];//     
	HeapSort(Edge, G.arcnum);//Edge 1-length
	int i = 0;
	for (i = 0; i < G.arcnum; i++)
		Vexset[i] = i;
	int v1, v2;//  
	int vs1, vs2;//    
	//  
	ofstream outf;
	outf.open("C:\\Users\\Lenovo\\Desktop\\EdegeGraph.txt", ios::out);
	if (!outf) {
		cerr << "File couldn't be open" << endl;
		abort();
	}
	for (i = 1; i <= G.arcnum; i++) {
		v1 = Locate(G, Edge[i].Head);//Head  
		v2 = Locate(G, Edge[i].Tail);//Tail  
		vs1 = Vexset[v1];
		vs2 = Vexset[v2];
		if (vs1 != vs2) {
			cout << "start at point " << Edge[i].Head << " ,end at point " << Edge[i].Tail <<" value=" << Edge[i].lowCost << "
";//    
			outf << "start at point " << Edge[i].Head << " ,end at point " << Edge[i].Tail<<" value="<<Edge[i].lowCost<< "
";//    
			//        
			for (int j = 0; j < G.vernum; j++) {//  vs1 vs2    ，     vs1，            
				if (Vexset[j] == vs2)
					Vexset[j] = vs1;//     vs2    vs1
			}
		}
		//  vs1==vs2,  2            ，    ，            ,       
	}
	outf.close();
}

int main() {
	AMGraph G;
	createUDN(G);
	show_Graph(G);
	MiniSpanTree_Kruskal(G);
}
/*
    ：
7 9
a b c d e f g
a b 
a f 
b c 
b g 
f e 
e g 
e d 
c d
d g 
*/