cspanningtree.h

一个基于启发式算法的搬运工求解程序

/*
1.最小生成树
a)
static void CSpanningTree::Run(double *s, int n, int *result, int none);	
b)参数
s: 二维数组第一行的地址，用法见下面例子
n: 邻接矩阵的大小， n * n
result: 存储结果，顺序存储n - 1条边的两条边，也就是说result的大小为2 * (n - 1)个元素
none: 用户标示两点之间不可达的一个数值．
c)例子

#include "header.h"
#include <iostream>
using namespace std;

int main()
{
int s[4][4] = {
{0, 1, 5, 3},
{1, 0, -1, 2},
{5, -1, 0, 4},
{3, 2, 4, 0}};
int result[6];
int i;

CSpanningTree::Run(s[0], 4, result, -1);
for(i = 0; i < 3; i++)
cout << result[i * 2] << " ---- " << result[i * 2 + 1] << endl;

return 0;
}			  
*/

#pragma once
#include "CUnionSet.h"
#include <queue>
using namespace std;

class CEdge
{
public:
	CEdge(int _v1, int _v2, int _length): v1(_v1), v2(_v2), length(_length) {}
public:
	int v1;
	int v2;
	int length;
};

bool operator < (const CEdge &m, const CEdge &n);

class CSpanningTree
{
public:
	static void Run(double *s, int n, int *result, int none);	
};

void CSpanningTree::Run(double *s, int n, int *result, int none)
{
	priority_queue<CEdge> Q;
	int i;
	int j;
	CUnionSet<int> uset;
	CEdge edge(-1, -1, -1);

	for(i = 0; i < n; i++)
		for(j = i + 1; j < n; j++)
			if(*(s + i * n + j) != none)
			{
				Q.push(CEdge(i, j, *(s + i * n + j)));
				uset.MakeSet(i);
				uset.MakeSet(j);
			}
	i = 0;
	while(!Q.empty())
	{
		edge = Q.top();
		Q.pop();
		if(!uset.Together(edge.v1, edge.v2))
		{
			result[i++] = edge.v1;
			result[i++] = edge.v2;
			uset.JoinSet(edge.v1, edge.v2);
		}
	}
}

bool operator < (const CEdge &m, const CEdge &n)
{
	return m.length >= n.length;
}