組み合わせ数学実験——最小重み生成ツリーのPrimアルゴリズム

//////////////////////////////////////////////
//                                          //
//  Project Name: PrimTree                  //
//                                          //
//  File Name: P_Tree.h                     //
//                                          //
//  Author: Victor Zhang                    //
//                                          //
//  ID: 21*****92                           //
//                                          //
//  Create Date: May 20. 2009               //
//                                          //
//////////////////////////////////////////////

#include <iostream>
#include <fstream>

using namespace std;

struct Edge
{
	int point_a;
	int point_b;
	int weigh;
	Edge* next;
};

struct Point
{
	int value;
	Point* next;
};

class P_Tree
{
private:
	Edge* EdgeHead;
	Point* PHead;
	ofstream outputFile;
	int TotalWeigh;
	bool DelEdge(int, int);
	void DelAll();
	bool AddPoint(int);
	void FindNext();
	bool FindPoint(int);
public:
	P_Tree()
	{
		EdgeHead = NULL;
		PHead = NULL;
		TotalWeigh = 0;
		outputFile.open("Graph_output.txt", ios::out);
	};
	bool AddEdge(int, int, int);
	void Prim();
	bool ReadFromFile();
	~P_Tree()
	{
		if (EdgeHead) DelAll();
		TotalWeigh = 0;
		outputFile.close();
	};
};

//////////////////////////////////////////////
//                                          //
//  Project Name: PrimTree                  //
//                                          //
//  File Name: P_Tree.cpp                   //
//                                          //
//  Author: Victor Zhang                    //
//                                          //
//  ID: 21*****92                           //
//                                          //
//  Create Date: May 20. 2009               //
//                                          //
//////////////////////////////////////////////

#include <iostream>
#include <fstream>
#include <iomanip>

#include "P_Tree.h"

using namespace std;

bool P_Tree::AddEdge(int x, int y, int w)
{
	if (x == y) return false;
	if (!(this->EdgeHead))
	{
		Edge* pH = new Edge;
		if (!pH) return false;
		pH->next = NULL;
		pH->point_a = (x > y) ? x : y;
		pH->point_b = (x > y) ? y : x;
		pH->weigh = w;
		this->EdgeHead = pH;
		return true;
	}
	else
	{
		Edge* p = this->EdgeHead;
		Edge* pH;
		while ((p->next) && (p->next->weigh <= w))
		{
			p = p->next;
		};
		if ((p->next) && (p->weigh <= w))
		{
			pH = new Edge;
			if (!pH) return false;
			pH->next = p->next;
			pH->weigh = w;
			pH->point_a = (x > y) ? x : y;
			pH->point_b = (x > y) ? y : x;
			p->next = pH;
		}
		else if (p->weigh <= w)
		{
			pH = new Edge;
			if (!pH) return false;
			pH->next = NULL;
			pH->weigh = w;
			pH->point_a = (x > y) ? x : y;
			pH->point_b = (x > y) ? y : x;
			p->next = pH;
		}
		else
		{
			pH = new Edge;
			if (!pH) return false;
			pH->next = p;
			pH->weigh = w;
			pH->point_a = (x > y) ? x : y;
			pH->point_b = (x > y) ? y : x;
			this->EdgeHead = pH;
		};
		return true;
	};
};

bool P_Tree::DelEdge(int x, int y)
{
	if (x == y) return false;
	Edge* p;
	Edge* pp;
	Edge* pc;
	p = this->EdgeHead;
	if (!p) return false;
	pp = p->next;
	if (x < y)
	{
		int t = x;
		x = y;
		y = t;
	};
	while (p && (p->point_a == x) && (p->point_b == y))
	{
		pp = p->next;
		delete p;
		p = pp;
		this->EdgeHead = pp;
	};
	if (!p) return true;
	pp = p->next;
	while (pp)
	{
		while (pp && (pp->point_a == x) && (pp->point_b == y))
		{
			pc = pp;
			pp = pp->next;
			delete pc;
			p->next = pp;
		};
		if (!pp) return true;
		p = pp;
		pp = p->next;
	};
	return true;
};

void P_Tree::DelAll()
{
	Edge* p;
	Point* pP;
	while (this->EdgeHead)
	{
		p = this->EdgeHead->next;
		delete this->EdgeHead;
		this->EdgeHead = p;
	};
	while (this->PHead)
	{
		pP = this->PHead->next;
		delete this->PHead;
		this->PHead = pP;
	};
};

bool P_Tree::AddPoint(int v)
{
	Point* p = new Point;
	p->value = v;
	p->next = this->PHead;
	this->PHead = p;
	return true;
};

bool P_Tree::FindPoint(int v)
{
	Point* p;
	p = this->PHead;
	while (p && (p->value != v))
		p = p->next;
	if (p) return true;
	return false;
};

void P_Tree::FindNext()
{
	if (!(this->EdgeHead)) return;
	if (!(this->PHead))
	{
		this->outputFile<<"("<<this->EdgeHead->point_a<<","<<this->EdgeHead->point_b<<")
";
		cout<<"("<<this->EdgeHead->point_a<<","<<this->EdgeHead->point_b<<")
";
		this->AddPoint(this->EdgeHead->point_a);
		this->AddPoint(this->EdgeHead->point_b);
		this->TotalWeigh += this->EdgeHead->weigh;
		this->DelEdge(this->EdgeHead->point_a, this->EdgeHead->point_b);
		return;
	}
	else
	{
		int NewP;
		Edge* p;
		Point* pP;
		p = this->EdgeHead;
		while(p)
		{
			if (this->FindPoint(p->point_a))
			{
				this->outputFile<<"("<<p->point_a<<","<<p->point_b<<")
";
				cout<<"("<<p->point_a<<","<<p->point_b<<")
";
				NewP = p->point_b;
				this->TotalWeigh += p->weigh;
				this->AddPoint(NewP);
				pP = this->PHead;
				while (pP)
				{
					this->DelEdge(NewP, pP->value);
					pP = pP->next;
				};
				return;
			};
			if (this->FindPoint(p->point_b))
			{
				this->outputFile<<"("<<p->point_a<<","<<p->point_b<<")
";
				cout<<"("<<p->point_a<<","<<p->point_b<<")
";
				NewP = p->point_a;
				this->TotalWeigh += p->weigh;
				this->AddPoint(NewP);
				pP = this->PHead;
				while (pP)
				{
					this->DelEdge(NewP, pP->value);
					pP = pP->next;
				};
				return;
			};
			p = p->next;
		};
		return;
	};
};

void P_Tree::Prim()
{
	while (this->EdgeHead)
		this->FindNext();
	cout<<this->TotalWeigh<<endl;
	this->outputFile<<this->TotalWeigh<<endl;
};

bool P_Tree::ReadFromFile()
{
	ifstream inputFile ("Graph_data.txt", ios::in);
	if (!inputFile)
	{
		cout<<"Error in reading file :\"Graph_data.txt\"."<<endl;
		system("pause");
		return false;
	};
	try
	{
		int i;
		int j;
		int r;
		i = j = r = 0;
		inputFile>>i>>j>>r;
		if (!(this->AddEdge(i, j, r))) return false;
		while(inputFile>>i>>j>>r)
			if (!(this->AddEdge(i, j, r)))
				return false;
	}
	catch(...)
	{
		cout<<"Error in reading file :\"Graph_data.txt\"."<<endl;
		system("pause");
		inputFile.close();
		return false;
	};
	inputFile.close();
	return true;
};

//////////////////////////////////////////////
//                                          //
//  Project Name: PrimTree                  //
//                                          //
//  File Name: main.cpp                     //
//                                          //
//  Author: Victor Zhang                    //
//                                          //
//  ID: 21*****92                           //
//                                          //
//  Create Date: May 20. 2009               //
//                                          //
//////////////////////////////////////////////

#include <iostream>

using namespace std;

#include "P_Tree.h"

void main()
{
	P_Tree a;
	a.ReadFromFile();
	a.Prim();
	system("pause");
};