最小生成树问题
2019年1月1日
最小生成树问题
（写这个代码的时候博主身心俱疲，就没有优化代码的风格了，凑合着看吧）
【问题描述】
若要在n个城市之间建立通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络，是一个最小生成树问题。
【基本要求】
利用克鲁斯卡尔算法计算最小生成树，图用一个集合表示。
【测试数据】
【实现提示】
用一个结构体实现边，其中定义两个端点以及边的权值，图用一个结构体数组实现最后储存树用一个vector实现，这个算法其实挺简单的，就是反复找权值最小的边，如果边的两个端点连通则跳过，因此需要额外维护一个点集合，每挑选一条边就将这条边的两个端点放入额外维护的那个点集合中，每挑选一条新的边就判断是否能在那个点集合中找到两个端点，若能，则两点连通。
【问题分析】
边结构体的定义为
struct node{
char first;
char second;
int value;
node(char a,char b,int c):first(a),second(b),value(c){}
node(){first='\0',second='\0',value=0;}
bool operator!=(const node &tmp){
return this->value != tmp.value?1:0;
}
void operator=(const node &tmp){
this->first = tmp.first;
this->second = tmp.second;
this->value = tmp.value;
}
};
其中，定义了两个构造器，一个是啥都不干的构造器，用来构造空边，这个空边最后遍历的时候用来判断遍历是否结束，另外一个就是我们用来真的构造边的构造器，然后还重载了两个运算符，
!=
用来判断遍历是否到结束，另外一个
=
用来直接对边集合赋值。
node *nodeList = (node*)malloc(sizeof(node)*100);
node node_;
for(int i=0;i<100;i++){
nodeList[i] = node_;
}
这个就是边集合的初始化。
cout<<"输入边的两个端点以及边的权值"<<endl;
cin>>one;
cin>>two;
cin>>three;
while(one != two){
nodeList[i_++] = node(one,two,three);
cout<<"输入边的两个端点以及边的权值"<<endl;
cin>>one;
cin>>two;
cin>>three;
}
这个用来初始化边。
for(int i=0;nodeList[i] != node_;i++){
for(int j=i;nodeList[j] != node_;j++){
if(nodeList[i].value > nodeList[j].value){
node temp = nodeList[i];
nodeList[i] = nodeList[j];
nodeList[j] = temp;
}
}
}
对边从小到大排序。
for(int i=0;nodeList[i] != node_;i++){
if(tmp.find(nodeList[i].first) == tmp.end() || tmp.find(nodeList[i].second) == tmp.end()){
edge.push_back(nodeList[i]);
tmp.insert(nodeList[i].first);
tmp.insert(nodeList[i].second);
}
}
for(int i=0;i<edge.size();i++){
cout<<"通信网络包括"<<edge[i].first<<edge[i].second<<endl;
}
这个就是实现的具体部分。
接下来就是完整的代码。
#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>
using namespace std;
struct node{
char first;
char second;
int value;
node(char a,char b,int c):first(a),second(b),value(c){}
node(){first='\0',second='\0',value=0;}
bool operator!=(const node &tmp){
return this->value != tmp.value?1:0;
}
void operator=(const node &tmp){
this->first = tmp.first;
this->second = tmp.second;
this->value = tmp.value;
}
};
int main(){
vector<node> edge;
node *nodeList = (node*)malloc(sizeof(node)*100);
node node_;
set<char> tmp;
char one,two;
int three;
int i_ = 0;
for(int i=0;i<100;i++){
nodeList[i] = node_;
}
cout<<"输入边的两个端点以及边的权值"<<endl;
cin>>one;
cin>>two;
cin>>three;
while(one != two){
nodeList[i_++] = node(one,two,three);
cout<<"输入边的两个端点以及边的权值"<<endl;
cin>>one;
cin>>two;
cin>>three;
}
for(int i=0;nodeList[i] != node_;i++){
for(int j=i;nodeList[j] != node_;j++){
if(nodeList[i].value > nodeList[j].value){
node temp = nodeList[i];
nodeList[i] = nodeList[j];
nodeList[j] = temp;
}
}
}
edge.clear();
for(int i=0;nodeList[i] != node_;i++){
if(tmp.find(nodeList[i].first) == tmp.end() || tmp.find(nodeList[i].second) == tmp.end()){
edge.push_back(nodeList[i]);
tmp.insert(nodeList[i].first);
tmp.insert(nodeList[i].second);
}
}
for(int i=0;i<edge.size();i++){
cout<<"通信网络包括"<<edge[i].first<<edge[i].second<<endl;
}
return 0;
}