smalltree.h

演示了最小生成树的普林算法和克鲁斯卡尔算法得算法过程。

// Smalltree.h: interface for the Smalltree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SMALLTREE_H__D37808A5_303C_4904_8A6C_12B882A27FA9__INCLUDED_)
#define AFX_SMALLTREE_H__D37808A5_303C_4904_8A6C_12B882A27FA9__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
//我的定义
#define N 10
#define ARCN 18;
#define MAX 10000
//#include <queue>
#include <string>
using namespace std;
//finished
struct VEXS
{
	char data;
	int pos;
	VEXS(char d,int i)
	{
		data = d;
		pos = i;
	}
	VEXS()
	{
		data = '\0';
		pos = 0;
	}
};
struct EDGE
{
	int fromvex;
	int endvex;
	int weight;
};
struct CEDGE
{
	char fromvex;
	char endvex;
	int weight;
};
struct Map
{
	VEXS vexs[N];
	int arcs[N][N];
	int vexnum;
	int arcnum;
	Map()
	{
		vexnum = 10;
		arcnum = 18;
		vexs[0] = VEXS('A',0);
		vexs[1] = VEXS('B',1);
		vexs[2] = VEXS('C',2);
		vexs[3] = VEXS('D',3);
		vexs[4] = VEXS('E',5);
		vexs[5] = VEXS('F',7);
		vexs[6] = VEXS('G',10);
		vexs[7] = VEXS('H',12);
		vexs[8] = VEXS('I',13); 
		vexs[9] = VEXS('J',15);
		for(int i=0;i<N;i++)
			for(int j = 0;j<N;j++)
				arcs[i][j] = MAX;

		arcs[0][1] = arcs[1][0] = 2;
		arcs[0][4] = arcs[4][0] = 4;
		arcs[0][7] = arcs[7][0] = 3;
		arcs[1][2] = arcs[2][1] = 6;
		arcs[1][4] = arcs[4][1] = 3;
		arcs[2][3] = arcs[3][2] = 7;
		arcs[3][4] = arcs[4][3] = 8;
		arcs[3][5] = arcs[5][3] = 12;
		arcs[4][5] = arcs[5][4] = 5;
		arcs[4][6] = arcs[6][4] = 3;
		arcs[4][7] = arcs[7][4] = 1;
		arcs[4][8] = arcs[8][4] = 1;
		arcs[5][6] = arcs[6][5] = 9;
		arcs[5][9] = arcs[9][5] = 6;
		arcs[6][8] = arcs[8][6] = 4;
		arcs[6][9] = arcs[9][6] = 8;
		arcs[7][8] = arcs[8][7] = 10;
		arcs[8][9] = arcs[9][8] = 9;
	}
};

class Pos
{
public:
	CPoint vpoint;
	int weight;
	Pos(CPoint point,int w)
	{
		vpoint.x = point.x;
		vpoint.y = point.y;
		weight = w;
	}
	Pos()
	{
		vpoint.x = vpoint.y = 0;
		weight = MAX;
	}
	Pos(const Pos& p)
	{
		vpoint.x = p.vpoint.x;
		vpoint.y = p.vpoint.y;
		weight = p.weight;
	}

	Pos& operator=(const Pos& p)
	{
		vpoint.x = p.vpoint.x;
		vpoint.y = p.vpoint.y;
		weight = p.weight;
		return *this;
	}
};
/*struct queue
{
	int size;
	Pos pos[100];
public:
	int qfront;
	int qrear;

	queue()
	{
		qfront = 0;
		qrear = 0;
		size = 0;		
	}
	
	inline Pos front()
	{
		Pos p;
		if(size == 0)
		{
			Pos pp;
			return pp;
		}
		else
		{
			p = pos[qfront];
			qfront++;
			return p;
		}
		
	}
	void pop()
	{
		if(size == 0)
			return;
		else
		{
			qfront++;
			size--;
			return;
		}
	}

	bool empty()
	{
		if(size == 0)
			return true;
		return false;
	}
	void push(Pos p)
	{
		pos[qrear] = p;
		qrear++;
		return;
	}
};*/

class Smalltree  
{
	int save[N];	
	CRect rect;
public:
	Map graph;
	CPoint vpoint[N];
	//queue<Pos> posvex;
	//queue<Pos> kposvex;
	Smalltree();
	virtual ~Smalltree();
	int prime(Pos pvex[]);
	bool find(char s[],char ch);
	int kruscal(Pos kvex[]);
	void putvpoint(CRect r);
};

#endif // !defined(AFX_SMALLTREE_H__D37808A5_303C_4904_8A6C_12B882A27FA9__INCLUDED_)