graph.cpp

旅行商问题问题的二叉树求解方法

#include "graph.h"
#include "share.h"
#include <stdio.h>
#include<stdlib.h>
#include <limits.h>

/************************************************************************/
/*从文件中读入图像信息并构成图像
/************************************************************************/
graph* creatgraph(char* s)
{
	FILE *fp = fopen(s,"r");//打开文件
	if (!fp) {
		printf("Can't open the file!");
		exit(0);
	}
	//申请空间并生成图像信息
	graph* g=(graph*)malloc(sizeof(graph));
	fscanf(fp,"%d",&g->vernum);
	fscanf(fp,"%d",&g->arcnum);
	int n=g->vernum;
	int * mat=(int *)malloc(sizeof(int)*n*n);//获得图像邻接矩阵
	if (!mat) {
		printf("memory flow!");
		exit(0);
	}
	for (int i=0;i<n;i++ ) {
		for (int j=0;j<n;j++) {
			fscanf(fp,"%d",&mat[i*n+j]);
		}
	}
	g->nermat = mat;
	g->suit = false;
	return(g);
}

/************************************************************************/
/*得到图像的边信息
/************************************************************************/
void getarcinfo(graph* g,arc * a)
{
	int num = 0;
	int n= g->vernum;
	int *t = g->nermat;
	for (int i=0;i<n;i++) {//无向图，只用扫描其中的一半
		for (int j=0;j<=i;j++) {
			if(t[i*n+j]>0)
			{
				a[num].start = i;
				a[num].end = j;
				a[num++].weight = t[i*n+j];
			}
		}
	}
}
/************************************************************************/
/*对图像进行旅行商问题搜索
/************************************************************************/
int* TSP(graph* g)
{
	int n=g->arcnum;
	int vn = g->vernum;
	int d=INT_MAX;
	bool first = true;//判断石构继续循环
	bool seccess = false;//是否找到适合的路径
	arc* a= (arc*)malloc(sizeof(arc)*n);
	getarcinfo(g,a);//获得图像边的信息
	sort(a,n);//对各个边进行排序
	int * ser = (int *)malloc(sizeof(int)*(vn+1));//当前序列
	int * path = (int *)malloc(sizeof(int)*(vn+1));//路径储存
	for (int i=0;i<vn;i++) {
		path[i] = -1;
	}
	for (int j=0;j<vn;j++) {
		ser[j]=j;
	}
	int k=1;int num=vn;
	while (k<=vn) {
		while (!seccess) {
			getarc(a,ser,vn);//得到当前路径的总长度
			if (ser[vn]>d) {//比最短路径长
				num=vn-1;
				while (ser[num]==ser[num-1]+1) {
					num--;
				}
				if (num == vn-k) {
					break;//跳出被循环
				}
				else{//寻找更短的路径
					ser[num-1]++;
					for (int i=num;i<vn;i++) {
						ser[i]=ser[i-1]+1;
					}
				}
			}else{
				first = false;
				if (test(a,ser,vn)) {//判断时候构成回路
					d=ser[vn];//保存路径信息
					for (int i=0;i<=vn;i++) {
						path[i]=ser[i];
					}
					seccess = true;
					break;
				}
				else{
					num=1;//寻找下一条路径
					while (ser[vn-num]==n-num) {
						num++;
					}
					ser[vn-num]++;
					for (int i=vn-num+1;i<vn;i++) {
						ser[i] = ser[i-1]+1;
					}
				}

			}
		}
		if (first) {
			break;
		}
		k++;
		seccess = false;
		first = true;
		for (int j=0;j<vn-k;j++) {
			ser[j] = j;
		}
		while (j<vn) {
			ser[j] = j+1;
			j++;
		}

	}
	for (int i=0;i<vn;i++) {
		if(path[i] == -1)
		{
			printf("there is even not a circle!\n");
			return(NULL);
		}
	}
	shoepath(a,path,vn);//显示路径信息
	free(a);
	free(ser);
	return(path);
}
/************************************************************************/
/*根据边的序号显示旅行商的路径信息
/************************************************************************/
void shoepath(arc* a,int* ser,int n)
{
	int num=n-1;
	bool * over = (bool*)malloc(sizeof(bool)*n);
	int set = a[ser[0]].end;
	over[0] =true;
	for (int i=1;i<n;i++) {
		over[i] = false;
	}
	printf("MiniLength:%d\n",ser[n]);
	printf("%d->",a[ser[0]].start+1);
	while (num>0) {
		for (int i=0;i<n;i++) {
			if (!over[i]) {
				if (a[ser[i]].start == set) {
					printf("%d->",a[ser[i]].start+1);
					set = a[ser[i]].end;
					over[i] = true;
					break;
				}else if(a[ser[i]].end == set){
					printf("%d->",a[ser[i]].end+1);
					set = a[ser[i]].start;
					over[i] = true;
					break;
				}
			}
		}
		num--;
	}
	printf("%d\n",set+1);
	free(over);
}
/************************************************************************/
/*根据当前的状态获取几条边
/************************************************************************/
void getarc(arc* a,int *ser,int n)
{
	ser[n] = 0;
	for (int i=0;i<n;i++) {
		ser[n] += a[ser[i]].weight;
	}
}

/************************************************************************/
/*测试这几条边能不能构成回路
/************************************************************************/
bool test(arc*a,int* ser,int n)
{
	int num=n;
	bool * over = (bool*)malloc(sizeof(bool)*n);
	bool get = false;
	for (int i=0;i<n;i++) {
		over[i] = false;
	}
	int set = a[ser[0]].end;
	over[0] =true;
	num--;
	while (num>0) {
		for (int i=0;i<n;i++) {
			if (!over[i]) {
				if (a[ser[i]].start == set) {
					set = a[ser[i]].end;
					over[i] = true;
					get =true;
					break;
				}else if(a[ser[i]].end == set){
					set = a[ser[i]].start;
					over[i] = true;
					get = true;
					break;
				}
			}
		}
		if (!get) {
			free(over);
			return(false);
		}
		num--;
		get = false;
	}
	free(over);
	if (set == a[ser[0]].start) {
		return(true);
	}else{
		return(false);
	}

}