smalltree.cpp

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

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

#include "stdafx.h"
#include "Graph.h"
#include "Smalltree.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

void Smalltree::putvpoint(CRect r)
{
	rect = r;
	vpoint[0].x = 2*rect.right/44;
	vpoint[0].y = 2*rect.bottom/44;
	vpoint[1].x = 8*rect.right/44;
	vpoint[1].y = 2*rect.bottom/44;
	vpoint[2].x = 14*rect.right/44;
	vpoint[2].y = 2*rect.bottom/44;
	vpoint[3].x = 20*rect.right/44;
	vpoint[3].y = 2*rect.bottom/44;
	vpoint[4].x = 2*rect.right/44;
	vpoint[5].x = 8*rect.right/44;
	vpoint[6].x = 14*rect.right/44;
	vpoint[7].x = 20*rect.right/44;
	vpoint[8].x = 2*rect.right/44;
	vpoint[9].x = 8*rect.right/44;
	vpoint[10].x = 14*rect.right/44;
	vpoint[11].x = 20*rect.right/44;
	vpoint[12].x = 2*rect.right/44;
	vpoint[13].x = 8*rect.right/44;
	vpoint[14].x = 14*rect.right/44;
	vpoint[15].x = 20*rect.bottom/44;
	vpoint[4].y = 8*rect.bottom/44;
	vpoint[5].y = 8*rect.bottom/44;
	vpoint[6].y = 8*rect.bottom/44;
	vpoint[7].y = 8*rect.bottom/44;
	vpoint[8].y = 14*rect.bottom/44;
	vpoint[9].y = 14*rect.bottom/44;
	vpoint[10].y = 14*rect.bottom/44;
	vpoint[11].y = 14*rect.bottom/44;
	vpoint[12].y = 20*rect.bottom/44;
	vpoint[13].y = 20*rect.bottom/44;
	vpoint[14].y = 20*rect.bottom/44;
	vpoint[15].y = 20*rect.bottom/44;
}

Smalltree::Smalltree()
{

}

Smalltree::~Smalltree()
{

}

int Smalltree::prime(Pos pvex[])
{
	int count = 0;
	int i,j,k,min,t,m,w,n;
	EDGE adges[N];
	EDGE temp;
	n = graph.vexnum;
	for(i=1;i<n;i++)
	{
		adges[i].fromvex = 0;
		adges[i].endvex = i;
		adges[i].weight = graph.arcs[0][i];
	}
	for(k=1;k<n;k++)
	{
		min = adges[k].weight;
		m = k;
		for(j = k+1;j<n;j++)
		{
			if(adges[j].weight < min)
			{
				min = adges[j].weight;
				m = j;
			}
		}

		if(k != m)
		{
			temp = adges[k];
			adges[k] = adges[m];
			adges[m] = temp;
		}
		j = adges[k].endvex;
		pvex[count].vpoint.x = adges[k].fromvex;
		pvex[count].vpoint.y = adges[k].endvex;
		pvex[count].weight = adges[k].weight;
		count++;
		
		for(i = k+1;i<n;i++)
		{
			t = adges[i].endvex;
			w = graph.arcs[j][t];
			if(w < adges[i].weight)
			{
				adges[i].weight = w;
				adges[i].fromvex = j;
			}
		}
	}
	return count;
}

bool Smalltree::find(char* s,char ch)
{
	//char *p = s;
	int i = 0;
	while(!(s[i] == '\0'))
	{
		if(s[i] == ch)
			break;
		else
			i++;
	}
	if(s[i] == '\0')
		return false;
	else
		return true;
}


int Smalltree::kruscal(Pos kvex[])
{
	int count = 0;
	CEDGE adges[18];
	CEDGE temp;
	char vs[N][N];
	char empty[] = "\0";
	int i,j,k,r,n,e;;
	n = graph.vexnum;
	e = graph.arcnum;
	r = 0;
	for(i = 0; i < n;i++)
	{
		vs[i][0] = i+'0';
		vs[i][1] = '\0';
		for(j = i+1;j<n;j++)
		{
			if(graph.arcs[i][j] != MAX)
			{
				adges[r].fromvex = i + '0';
				adges[r].endvex = j + '0';
				adges[r].weight = graph.arcs[i][j];
				r++;
			}
		}
	}

	for(i = 0;i<e-1;i++)
	{
		k = i;
		for(j = i+1;j < e;j++)
		{
			if(adges[j].weight < adges[k].weight)
				k = j;
			if(k != i)
			{
				temp = adges[k];
				adges[k] = adges[i];
				adges[i] = temp;
			}
		}
	}
	r = -1;
	for(k = 0;k < e; k++)
	{
		i = 0;
		j = 0;
		while(1)
		{
			if((vs[i][0] != '\0') && (find(vs[i],adges[k].fromvex) == true))
				break;
			else
				i++;
		}//vs[i][0] != '\0' &&}
		while(1)
		{
			if((vs[j][0] != '\0') && (find(vs[j],adges[k].endvex) == true))
				break;
			else
				j++;		
		}//&& vs[i][0] != '\0'
		if(i != j)
		{
			strcat(vs[i],vs[j]);
			strcpy(vs[j],empty);
			save[++r] = k;
		}
	}
		
	for(i = 0;i<=r;i++)
	{
		//posvex.push(Pos(CPoint(adges[save[i]].fromvex,adges[save[i]].endvex),adges[save[i]].weight));
		kvex[count].vpoint.x = adges[save[i]].fromvex - '0';
		kvex[count].vpoint.y = adges[save[i]].endvex - '0';
		kvex[count].weight = adges[save[i]].weight;
		count++;
	}
	
	return count;
}