grape.cpp

最小生成树的kruskal算法实现 使用mfc显示界面（可以随机生成边）

// Grape.cpp: implementation of the Grape class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MSTkruskal.h"
#include "Grape.h"
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Grape::Grape()
{

}

Grape::~Grape()
{

}

void Grape::GenerateEdge()
{
	int i, j;
	const int valuemax = 100;
	const int possibility = 2;
	srand(time(NULL));
	for (i = 0; i < vp.size(); ++i)
	{
		for (j = i + 1; j < vp.size(); ++j)
		{
			int b = rand() % possibility;
			int v = (rand() % valuemax) + 1;
			if (b == 0)
			{
				MyEdge e(vp[i], vp[j], v);
				ve.push_back(e);
			}
		}
	}
	SortEdge(0);
	return;
}

void Grape::SortEdge(int inc)
{
	sort(ve.begin(), ve.end());
}

inline int findset(const vector<int>& v, int i)
{
	while (v[i] != -1)
	{
		i = v[i];
	}
	return i;
}

void Grape::FindMST()
{
	std::vector<int> vid;
	int i;
	for (i = 0; i < vp.size(); ++i)
	{
		vid.push_back(-1);
	}
	//SortEdge(0);
	for (i = 0; i < ve.size(); ++i)
	{
		int id1 = ve[i].p1.id;
		int id2 = ve[i].p2.id;
		int r1 = findset(vid, id1);
		int r2 = findset(vid, id2);
		if (r1 != r2)
		{
			vid[r2] = r1;
			vIDofMSTEdge.push_back(i);
		}
	}
}