一笔画问题的c++实现

一笔画问题，即欧拉回路问题，最近在算法课上老师留了这个作业，下面将我的实现说一下。首先，先将问题描述一下。

该图中节点编号从上至下，从左至右编号如下
  1   2
3 4 5 6
7 8 9 10 11
   12 13
  14 15 16
要求：从节点1开始，一笔将该图形画出。
首先讲下该题的大概思路：
概括的讲是先找小回路，再并小回路。
（1）先将1放入访问队列中，寻找1的未访问过的邻接边，将满足这样条件的边中另一顶点值最小的顶点放入访问队列中，再从这个点出发继续寻找，直至找到的变的另一顶点与队列头部顶点相等（这时说明找到了一条小回路），将找到的第一个小回路的边标记为1；若队列头顶点还存在另一小回路，则继续寻找另一小回路；否则要将队列头结点删除，开始下一点的查找。
（2）将图中所有边都标记后，再从1开始，找与该点邻接的边中值最大的边的另一点，若存在多个边值一样的边，则先从顶点值较小的点开始，并将当前访问的点设置为该点，再往下找。
说了这么多，还是感觉不大明白。用本题的具体数字说明一下。
第一次找小回路1-3-4-1
第二次3-7-8-3
第三次4-8-9-4
第四次9-5-2-6-5-10-6-11-10-9
。。。。。。
在访问队列中存储的节点
1，3，4，7，8，9，5，2，6，10，11，12，13，14，15，16

#include<queue>
#include<iostream>
#include<fstream>
#include<string>
#define MAX 1000
using namespace std;
int main(){
	ifstream fin("input2.txt");
	ofstream fout("output.txt");
	int m,n,start,end;
	int i,j;
	int now,front;
	int flag = 1;//边的标记
	int count = 2;
	int cycleSt = 1;//一笔画的起点
	int cycleEnd = 1;//一笔画的终点
	int minNode=9999;
	int maxEdge = 0;
	fin>>m>>n;//m:图中点数，n:输入文件数据行数
	int **edge = new int*[m+1];//图的连通二维数组表示
	for(i=0;i<m+1;i++)
		edge[i] = new int[m+1];
	bool *inQueue = new bool[m+1];//图中顶点的访问队列标记，
	//若之前该顶点已放入队列中，那么该顶点标记为true
	//若该顶点从未放入队列中，那么该顶点标记为false
	for(i=1;i<m+1;i++)
		inQueue[i]=false;
	//初始化连通图，值为MAX则说明未连通
	for(i=0;i<m+1;i++)
		for(j=0;j<m+1;j++)
			edge[i][j]=MAX;
	queue<int> q;//顶点访问队列
	fin>>start>>end;
	q.push(start);//先将起始点放入访问队列中
	edge[end][start]=edge[start][end]=0;
	while(count<=n){
		fin>>start>>end;
		edge[start][end]=edge[end][start]=0;
		count++;
	}
	front = q.front();//小回路的起点
	now = q.front();//目前正在访问的点
	inQueue[now]=true;//把起点标记为true，表示已放入过队列
	do{
		for(i=1;i<m+1;i++){
			if(edge[now][i]==0){//如果与起点邻接的某边未走过
				edge[i][now]=edge[now][i]=flag;//标记该边
				if(i!=front&&!inQueue[i]){
					q.push(i);//把与该边邻接的另一顶点放入队列
					inQueue[i] = true;//将该点放入过队列的标记设置为true
				}
				now = i;//下一步开始从这一点出发
				break;
			}
		}
		if(i==m+1){//如果某个点相邻接的边都访问过，那么将该点从访问队列中删除，并访问下一个点
			cout<<front<<" ";
			q.pop();
			if(!q.empty()){
				now = q.front();
				front = q.front();
			}
		}
		else if(now==front){//如果现在访问的点是小回路的起点
			//首先查看该回路是否有其他的回路存在
			for(i=1;i<m+1;i++){
				if(edge[now][i]==0)break;
			}
			//没有其他未访问的边了，删除头结点，访问下一结点，并将边标记加1
			if(i==m+1){
				cout<<front<<" ";
				q.pop();
				if(!q.empty()){
					now=q.front();
					inQueue[now]=true;
					front = q.front();
				}
				flag++;
			}else{//若还有其他未访问的边，则将边标记加1后，走新的小回路
				now = front;
				flag++;
			}
		}
	}while(!q.empty());
	/*for(i=1;i<m+1;i++)
		for(j=1;j<m+1;j++)
			fout<<edge[i][j]<<" ";
		fout<<endl;*/
	now = cycleSt;
	cout<<"一笔画的路线是:"<<endl<<now<<"->";
	while(true){
		maxEdge = 0;
		minNode = 9999;
		for(i=1;i<m+1;i++){
			//在边标记不同的情况下，找表标记最大的边的邻接点
			//在边标记相同的情况下，找节点值最小的邻接点
			if(edge[now][i]>maxEdge&&edge[now][i]!=MAX){
				maxEdge = edge[now][i];
				//edge[i][now]=edge[now][i]=MAX;
				minNode = i;
				//break;
			}
		}
		if(minNode==9999){
			cout<<"未能找到一笔画路线"<<endl;
			break;
		}else{
		edge[minNode][now]=edge[now][minNode]=MAX;//访问后，将连通边设置为不连通
		now = minNode;
		if(now==cycleEnd) {cout<<now;break;}//如果起点和终点相等，则退出循环
		else cout<<now<<"->";
		}
	}
	return 0;
}

呵呵，讲的可能不是很清楚，有不懂的可以问我，希望大家可以在这探讨，源程序及输入文件见压缩包附件。
PS：感谢杨老师的算法课，这位老教授的课很有趣，我也收获了很多。

评论

2 楼 绝缘君 2016-12-19  

博主的算法思路很棒......我运行不出是编译器的原因吗= =

1 楼 绝缘君 2016-12-19  

为啥代码运行不出来报错：0x746BA832 处(位于 Project1.exe 中)有未经处理的异常: Microsoft C++ 异常: std::bad_array_new_length，位于内存位置 0x006FF590 处。