C++最小生成树，求全代码

现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？
    【输入】第一行两个数v(1≤ v≤100),e，分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权
    【输出】v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。

答案：实在抱歉，昨天的代码有点小错误，做下改正：
//Minim_tree.cpp
#include "Minim_tree.h"
#include <iostream>
using namespace std;
Edge::Edge()
{
}

Minim_tree::Minim_tree()
{
 this->city = 0;
 this->line = 0;
 this->Ed_len = 1;
 this->Re_len = 1;
 this->CreatEdgesetArray();
}
void Minim_tree::CreatEdgesetArray()     //构建无线网络
{
 int cit,lin,i,j,w;
 cout<<"输入城市数,网络数:"<<endl;
 scanf("%d %d",&cit,&lin);
 this->city = cit;
 this->line = lin;
 cout<<"请输入各网络边："<<endl;
 for(int k=1;k<=this->line;k++)
 {
  fflush(stdin);
  scanf("%d %d %d",&i,&j,&w);
  this->EderSet[k].fromvex = i;
  this->EderSet[k].endvex = j;
  this->EderSet[k].weight = w;
 }
 this->SetOrder();
}
void Minim_tree::SetOrder()        //按权值升序排序
{
 Edge temp;
 for(int i = 1;i<=this->line-1;i++)
  for(int j=i+1;j<=this->line;j++)
  {
   if(this->EderSet[i].weight>this->EderSet[j].weight)
   {
    temp = this->EderSet[i];
    this->EderSet[i] = this->EderSet[j];
    this->EderSet[j] = temp;
   }
  }
  for(int i=1;i<=this->line-1;i++)
   cout<<this->EderSet[i].fromvex<<","<<this->EderSet[i].endvex<<","<<this->EderSet[i].weight<<endl;
}
void Minim_tree::Cruskal()
{
 int matrix[E][E];              //此集合用来判断选定的边是否符合克鲁斯卡尔算法的条件          
 for(int i=1;i<=this->line;i++)           //初始化集合，使每个懂点分属于对应的集合
  for(int j=1;j<=this->line;j++)
  {
   if(i==j)
    matrix[i][j]=1;   // 每一个点和它自身都是连通的
   else
    matrix[i][j]=0;
  }
  int k=1 ,m1,m2;
  while(k<this->line)
  {
   for(int i=1;i<=this->line;i++)             //取边所在两定点集合所在的序号
   {
    if(matrix[i][this->EderSet[this->Ed_len].fromvex] == 1)
     m1=i;
    if(matrix[i][this->EderSet[this->Ed_len].endvex] == 1)
     m2=i;
   }
         if(m1!=m2)                            //若不等则没有连通
   {
    this->Resul_Set[this->Re_len] = this->EderSet[this->Ed_len];
    this->Re_len++;
    
    for(int j=1;j<=this->line;j++)
    {
     matrix[m1][j] = matrix[m1][j]||matrix[m2][j];    //合并两个集合
     matrix[m2][j] = 0;                              //置为空集
    }
   }
     this->Ed_len++;
     k++;
  }
}

void Minim_tree::Print()
{
 cout<<"根据Cruslkal算法得出以下结果（不唯一）:"<<endl;
 for(int i=1;i<this->Re_len;i++)
 {
  cout<<this->Resul_Set[i].fromvex<<","<<this->Resul_Set[i].endvex<<","<<this->Resul_Set[i].weight<<endl;
 }
}
Minim_tree::~Minim_tree(void)
{
}
这是个稠密图，所以用Cruslkal算法选边。另外你2,4和3,4的权值是一样的，所以最终得到的结果会有2组，我只选了一种情况。下面是代码：
//Minim_tree.h
#pragma once
const int E =20;
class Edge
{
public:
 Edge();
 int fromvex;   //起点
 int endvex;    //终点
 int weight;    //权值
};
class Minim_tree
{
public:
 Minim_tree(void);
 void CreatEdgesetArray();
 void Cruskal();
 void SetOrder();
 void Print() ;
 ~Minim_tree(void);
private:
 Edge EderSet[E+1];
 int Ed_len;
 int Re_len;
 Edge Resul_Set[E+1];
 int city;            //点
 int line;             //线
};
----------------------------------------------------------------------------------------------------------
//Minim_tree.cpp
#include "Minim_tree.h"
#include <iostream>
using namespace std;
Edge::Edge()
{
}

Minim_tree::Minim_tree()
{
 this->city = 0;
 this->line = 0;
 this->Ed_len = 1;
 this->Re_len = 1;
 this->CreatEdgesetArray();
}
void Minim_tree::CreatEdgesetArray()     //构建无线网络
{
 int cit,lin,i,j,w;
 cout<<"输入城市数,网络数:"<<endl;
 scanf("%d %d",&cit,&lin);
 this->city = cit;
 this->line = lin;
 cout<<"请输入各网络边："<<endl;
 for(int k=1;k<=this->line;k++)
 {
  fflush(stdin);
  scanf("%d %d %d",&i,&j,&w);
  this->EderSet[k].fromvex = i;
  this->EderSet[k].endvex = j;
  this->EderSet[k].weight = w;
 }
 this->SetOrder();
}
void Minim_tree::SetOrder()        //按权值升序排序
{
 Edge temp;
 for(int i = 1;i<=this->Ed_len-1;i++)
  for(int j=i+1;j<=this->Ed_len;j++)
  {
   if(this->EderSet[i].weight>this->EderSet[j].weight)
   {
    temp = this->EderSet[i];
    this->EderSet[i] = this->EderSet[j];
    this->EderSet[j] = temp;
   }
  }
}
void Minim_tree::Cruskal()
{
 int matrix[E][E];              //此集合用来判断选定的边是否符合克鲁斯卡尔算法的条件          
 for(int i=1;i<=this->city;i++)           //初始化集合，使每个懂点分属于对应的集合
  for(int j=1;j<=this->city;j++)
  {
   if(i==j)
    matrix[i][j]=1;   // 每一个点和它自身都是连通的
   else
    matrix[i][j]=0;
  }
  int k=1 ,m1,m2;
  while(k<this->city)
  {
   for(int i=1;i<=this->city;i++)             //取边所在两定点集合所在的序号
   {
&nb

上一个：C++中字符串与字符数组问题
下一个：C++输出1-10 看看哪出错了