tin.txt

一种更简单

最小生成树算法 (C++实现)2007-01-27 18:51这个算法,不考虑点,只考虑边及权值,抛弃了以往的邻接矩阵,邻接链表等方式 ,而是直接用数组存储,节省空间,效率更高.

//=======================
//优化后的最小生成树算法
//=======================
#include <iostream>
#include <algorithm>
using namespace std;
//=======================
//边的结构体的定义
//-----------------------
struct Line
{
int begin;//边的开始点
int end;//边的结束点
double value;//线的权值
};
//=======================
//建堆时用的仿函数
//-----------------------
struct heap_f
{
bool operator()(Line a,Line b) const
{
   return a.value>b.value;
}
};
//===============================
//分区时用的仿函数,并判断有无回路
//-------------------------------
struct partition_f
{
int *pi;//用来存储边的开始点
partition_f(int n)
{
   pi = (int *)malloc(sizeof(int)*n);
   memset(pi,0,n);//将pi初始化为0
}
bool hasLoop(Line * line)//判断有无回路
{
   if(pi[line->begin]==1&&pi[line->end]==1)
    return true;
   else
   {
    pi[line->begin]=1;
    pi[line->end]=1;
    return false;
   }
}
bool operator()(Line line) const
{
   return( pi[line.begin]==1||pi[line.end]==1)&&!(pi[line.begin]==1&&pi[line.end]==1);
}
};
//================================
//主函数
//--------------------------------
int main()
{
int pointNum;//表示点的个数
int lineNum;   //表示边的个数
Line *posBegin,*posEnd;//表示边的开始位置和结束位置

cin>>pointNum>>lineNum;//读入点的个数和边的个数

Line *lineSet = (Line *)malloc(sizeof(Line)*lineNum);//定义动态的数组

int i =0;
while(cin>>lineSet[i].begin>>lineSet[i].end>>lineSet[i].value)++i; //从文件中读入数据(边)到数组里

partition_f pf(lineNum+1);//0下标空闲不用
pf.pi[1]=1;
posBegin =lineSet;
while(posBegin-lineSet<pointNum-1)
{
   posEnd = partition(posBegin,lineSet+lineNum,pf);//将数组分区
   make_heap(posBegin,posEnd,heap_f());//将第一区建堆
   if(!pf.hasLoop(posBegin))//确定没有回路
   {
       ++posBegin;
   }
}
for(Line * li = lineSet;li!=posBegin;++li)//输出最小生成树的各个边
   cout<<"("<<li->begin<<"   "<<li->end<<"   "<<li->value<<")"<<endl;
}
//================================

输入数据:(放到.txt文件里)

9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
4 6 14
3 6 4
7 6 2
7 8 1
8 9 7
3 9 2
2 8 11
1 8 8
7 9 6

输出结果:

(1 2 4)
(2 3 8)
(3 9 2)
(3 6 4)
(7 6 2)
(7 8 1)
(3 4 7)
(4 5 9)