halminton.cpp

Algorithm Hamilton I do with C++.It is easy for you

#include <conio.h>
#include <iostream.h>
#include "stackandqueue.h"
const maxv=999;
typedef struct tagnodenode
{
	int n;
	int m;
	int a[99][99];
;
}GRAPH;


node *p;	node *ke[maxv];

int CE[maxv];

void matranke(GRAPH &p)
{
	int x,y;

	cout<<"\n Nhap vao so dinh:";
	cin>>p.n;
	cout<<"\n Nhap vao so canh cua do thi:";
	cin>>p.m;

	for(int i=0;i<p.n;i++)
		for(int j=0;j<p.n;j++)
			p.a[i][j]=0;
		
	for(i=1;i<=p.m;i++)
	{
		cout<<"\n Dinh dau-Dinh cuoi cua canh thu "<<i<<" la:";
		cin>>x>>y;

				p.a[x][y]=p.a[y][x]=1;

	}
}
////////////chuyen tu ma tran ke sang danh sach ke/////////////////
////////////do thi vo huong//////////////////////////
void listnear(GRAPH q)
{
	for(int i=0;i<q.n;i++)
		ke[i]=NULL;
	for(i=0;i<q.n;i++)
		for(int j=0;j<=i;j++)
		{
			if(q.a[i][j]!=0&&q.a[j][i]!=0)
			{
				p=new node;
				p->info=j;
				p->pnext=ke[i];
				ke[i]=p;
				p=new node;
				p->info=i;
				p->pnext=ke[j];
				ke[j]=p;
			}
		}
		cout<<"\n Danh sach cac canh ke:";
		for(i=0;i<q.n;i++)
		{
			cout<<"\n danh sach ke cua dinh thu "<<i<<":\n";
			node *r;
			r=ke[i];
			while(r!=NULL)
			{
				cout<<r->info<<"\t\n";
				r=r->pnext;
			}
		}
}
void xuatmatran(GRAPH p);

////////////////////////////////////////////////////////////////////
///////////EULER//////////////////////////////
///////////////////////////////
LIST mystack;
/*
void Euler(int u)
{
	node *w=new node;
	node *v=new node;
	InitStack(mystack);
	Push(mystack,u);
	while(IsEmptyStack(mystack)!=0)
	{
		w->info=Top(mystack);
		
		if(ke[w->info]!=NULL)
		{
			v->info=ke[w->info]->info;//////////////lay y(o day y la v,x=w
			Push(mystack,v->info);
			///////xoa y la phan tu dau tien
			node *t1=new node;
			t1=ke[w->info];
			ke[w->info]=ke[w->info]->pnext;
			delete t1;
			/////////////xoa x trong dan hsach ke cua y(o day la xoa v trong dske cua w
			node *t2=ke[v->info];/////////////////v->=ke[v->x]->x(nhu nhau)
			//////////ngay tai vi tri dau tien la da co x
			if(t2->info==w->info)
			{
				ke[v->info]=ke[v->info]->pnext;
				delete t2;
		
			}
			else
			{
				
				while(t2!=NULL)
				{
					if((t2->pnext==NULL)&&(t2->info==w->info))///truong hop t2 la cuoi cung va y cung la cuoi cung
					{
						delete t2;
						break;
					}

					else
					{
						node *r=new node;
						r=t2->pnext;
						if(r==NULL)//truong hop t2 cuoi cung ma ko phai y
							break;
						if(r->info==w->info)
						{
							t2->pnext=r->pnext;
							delete r;
							break;
						}
					}
					t2=t2->pnext;
				}
			}
		}
		else
		{
			int i=0;
				cout<<"\n chu trinh euler:\n";
			while(IsEmptyStack(mystack)!=0)
			{
				CE[i]=Pop(mystack);
			
				cout<<"-->"<<CE[i];
				i++;
			}
			cout<<"\n";
		}
	}
}
*/
//////////////////////////////////////////////////////
////////HALMINTON////////////////////////////
/////////////////////////////////////////////







int insertt(int n)
{
	return n;
}
int tam=0;

void Halminton(int k,GRAPH g,int v0,int X[maxv],int chuaxet[maxv],node *kee[maxv],int AA[maxv],int &dem)
{
	node *y=new node;
	for(y=kee[X[k-1]];y!=NULL;y=y->pnext)
	{
		//bat dau tinh tu dinh 0
		if((k==g.n)&&(y->info==v0))

		{
			cout<<tam<<"   ";
			for(int j=0;j<g.n;j++)	
			{	
				cout<<"-->"<<X[j];
				AA[dem]=insertt(X[j]);
				dem++;
			}
			tam++;
				
			cout<<"-->"<<v0<<"\n";
		
		}
		else if(chuaxet[y->info])
		{
			X[k]=y->info;
			chuaxet[y->info]=0;
			Halminton(k+1,g,v0,X,chuaxet,kee,AA,dem);
			chuaxet[X[k]]=1;////////////Quay lui //////////////////
		}
	}
}
////insert cac gia tri X[j] vao mang


int IsEuler(GRAPH g)
{
	int t=0;
	node *p=new node;
	for(int i=0;i<g.n;i++)
	{
		p=ke[i];
		while(p!=NULL)
		{
			t++;
			p=p->pnext;
		}
		if(t%2!=0)
			return 0;
	}
	return 1;
}
int IsHalminton(GRAPH g)
{

	int t=0;
	
	for(int i=0;i<g.n;i++)
	{
		node *p=new node;
		p=ke[i];
		while(p!=NULL)
		{
			t++;
			p=p->pnext;
		}
		if((t<g.n/2) ||g.n<3)
			return 0;
	}
	return 1;
}



void main()
{
	GRAPH p;
	matranke(p);
	
	xuatmatran(p);
	int chuaxetx[maxv];
	int Mang[maxv];
	int demm=0;

	listnear(p);
	int XX[maxv];

	////////////
	if(IsEuler(p))
	{
		cout<<"\n do thi vua nhap la do thi euler:";
	//	Euler(1);
	}
	else
		cout<<"\n do thi vua nhap ko la do thi euler:\n";

	//////////////
	if(IsHalminton(p))
	{
		cout<<"\n chu trinh halminton:\n";
		for(int i=0;i<p.n;i++)
			chuaxetx[i]=1;///////////khoi tao chua xet
		int v0;
		cout<<"\n nhap vao dinh muon bat dau:";
		cin>>v0;
		XX[0]=v0;
		chuaxetx[v0]=0;//////danh dau da xet
		Halminton(1,p,v0,XX,chuaxetx,ke,Mang,demm);
	}
	else
		cout<<"\n Do Thi vua nhap ko phai la do thi Halminton:\n";

////////////////////////////////////////////////////////////////////////////
	///do thi xuat tu mot mang///////////////
	cout<<0<<"--";
	for(int i=1;i<demm;i++)
	{
		
		cout<<Mang[i]<<"--";
		
		if(Mang[i]==0)
		{
		
			cout<<"\n";
			if(i<demm)
				cout<<0<<"--";
		}
	}
	cout<<0<<"--";
	cout<<"\n";
	


}
void xuatmatran(GRAPH p)
{
	cout<<"\n ma tran la:\n";
	for(int i=0;i<p.n;i++)
	{
		for(int j=0;j<p.n;j++)
			cout<<p.a[i][j]<<"\t";
		cout<<"\n";
	}
}