graph.cpp

最小切割的近似算法。希望能够对大家有所参考

#include <stdio.h>
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include "graph.h"

graph::graph()
{
	int x, y;
	struct edge* ep;
	FILE* fp = fopen("map.txt", "r");
	if(fp==NULL)
	{
		printf("Load map fail!\n");
		return ;
	}

	fscanf(fp, "%d", &gsize);
	ssize = gsize;
	esize = 0;
	gsets = new set[gsize+1];
	vsid = new int[gsize+1];

	for(x=0; x<gsize; x++)
	{
		vsid[x] = x;
		gsets[x].edgenum = 0;
		gsets[x].vexnum = 1;
		gsets[x].setedges = new edge*[gsize];
		for(y=0; y<gsize; y++)
		{
			gsets[x].setedges[y] = new edge;
			gsets[x].setedges[y]->nextedge = NULL;
		}
	}

	while(fscanf(fp, "%d %d", &x, &y)!=EOF)
	{
		ep = new edge;
		ep->u = x, ep->v = y;
		ep->nextedge = gsets[x].setedges[y]->nextedge;
		gsets[x].setedges[y]->nextedge = ep;
		
		ep = new edge;
		ep->u = y, ep->v = x;
		ep->nextedge = gsets[y].setedges[x]->nextedge;
		gsets[y].setedges[x]->nextedge = ep;
		
		gedges[esize].u = x, gedges[esize].v = y;
		esize++;
	}
}

graph::~graph()
{
	int i, j;
	struct edge *ep, *pep;
	for(i=0; i<gsize; i++)
	{
		if(gsets[i].setedges != NULL)
		{
			for(j=0; j<gsize; j++)
			{
				ep = gsets[i].setedges[j]->nextedge;
				if(ep!=NULL)
				{
					pep = ep->nextedge;
					delete ep;
					ep = pep;
				}
			}
			delete []gsets[i].setedges;
		}
	}
}

void graph::process()
{
	int delno, index=0;
	const int et[4][2] = {{4,5}, {2,3},{3,4},  {1,4}};
	srand((unsigned)time(NULL));

	while(ssize>2)
	{
		delno = rand()%esize;
		//delno = et[index++];
		//DelEdge(gedges[delno].u, gedges[delno].v);
		MergeSet(vsid[ gedges[delno].u ], vsid[ gedges[delno].v] );
		//MergeSet(vsid[et[index][0]], vsid[et[index][1]]);
		index++;
	}
	cout << "random mini cut is " << esize << endl;
}

bool graph::DelEdge(int v1, int v2)
{
	int s1 = vsid[v1], s2 = vsid[v2], i, uu, vv;
	cout << "[" << v1 <<", " << v2 << "]" << endl;
	for(i=0; i<esize; i++)
	{
		uu = gedges[i].u, vv = gedges[i].v;
		if((uu==v1 && vv==v2) || (uu==v2 && vv==v1)) break;
	}
	for(; i<esize-1; i++) gedges[i] = gedges[i+1];
	esize--;
	return true;
}

bool graph::MergeSet(int s1, int s2)
{
	struct edge *ep, *pep;

	for(int i=0; i<gsize; i++)
		if(vsid[i]==s2) vsid[i]= s1;
	//删除两个集合之间的边
	ep = gsets[s2].setedges[s1]->nextedge;
	while(ep!=NULL)
	{
		// 将集合id较大的并入id号较小的集合
		pep = ep->nextedge;
		delete ep;
		ep = pep;
	}
	gsets[s2].setedges[s1]->nextedge = NULL;

	ep = gsets[s1].setedges[s2]->nextedge;
	while(ep!=NULL)
	{
		pep = ep->nextedge;
		DelEdge(ep->u, ep->v);
		delete ep;
		ep = pep;
	}
	gsets[s1].setedges[s2]->nextedge = NULL;
	
	for(i=0; i<gsize; i++)
	{
		if(gsets[s2].setedges[i]->nextedge!=NULL) //将s2与其他集合连接的边并入s1
		{
			ep = gsets[s1].setedges[i];
			while(ep->nextedge!=NULL) ep = ep->nextedge;
			ep->nextedge = gsets[s2].setedges[i]->nextedge; //s2相应集合的边链接在s1对应集合的末尾

			ep = gsets[i].setedges[s1];
			while(ep->nextedge!= NULL) ep=ep->nextedge;
			ep->nextedge = gsets[i].setedges[s2]->nextedge;

			gsets[i].setedges[s2]->nextedge = NULL;
		}
	}
	for(i=0; i<gsize; i++) delete gsets[s2].setedges[i];

	gsets[s2].setedges = NULL;
	ssize = ssize - 1;
	return true;
}