哈密尔顿环递归回溯.txt

都是自己编写的常用算法的事例,本人础作. 里面有:哈密尔顿环,皇后问题,图的着色问题,子集和数问题,树和等价问题,栈的各种用发等.

#include<cstdlib>
#include<iostream>
using namespace std;

bool Graph[101][101];  //经过编程验证,全局数组默认赋值为0
int X[101]={0};        //解空间，记录结点的序号
const int N = 5;      //结点的个数 



bool check( int k)
{
	int i;
	for(i = 1;i<k;i++)  // 不能走回头路
	{
		if(X[k] == X[i])
			return false;
	}
	if( k > 1)         //与前一个结点应该有边相连
	{
		int indexPre = X[k-1];
		int indexCurr = X[k];
		if(!Graph[indexPre][indexCurr])
			return false;
	}
	return true;
}

void show_result()
{
	int i;
	cout<<endl<<"-------------------"<<endl;
	for(i =1; i<=N; i++)
		cout<<X[i]<<"   ";
	cout<<endl;
}
void select_node( int k)
{
	//选择第k个要遍历的结点
	
	int i;
	for(i=1;i<=N;i++)
	{
		X[k] = i;
		if(check(k))  //如果符合规则则进行下列操作，否则进入下次循环
		{
			if( k == N)
			{
				int first = X[1];
				int last = X[N];
				if(Graph[first][last])
				{
				  show_result();
				}
			}
			else
				select_node(k+1);
		}
	}//for
}
void main()
{
	
	Graph[1][1]=0; Graph[1][2]=1;  Graph[1][3]=0; Graph[1][4]=1;  Graph[1][5]=1;
	Graph[2][1]=1; Graph[2][2]=0;  Graph[2][3]=1; Graph[2][4]=1;  Graph[2][5]=1;
	Graph[3][1]=0; Graph[3][2]=1;  Graph[3][3]=0; Graph[3][4]=1;  Graph[3][5]=0;
	Graph[4][1]=1; Graph[4][2]=1;  Graph[4][3]=1; Graph[4][4]=0;  Graph[4][5]=0;
	Graph[5][1]=1; Graph[5][2]=1;  Graph[5][3]=0; Graph[5][4]=0;  Graph[5][5]=0;

    select_node(1);
	cout<<"inputing ends"<<endl;
	
}