一笔画路径生成（c++版）

一笔画 路径生成（c++）

练习图的遍历、回溯

新建一个OnePen类；
使用setNodeNum()方法设置节点数量；
使用setNodeJoin()设置节点连线；
执行drawLine()方法即可得出该图的一笔画路线；

• main.cpp

#include <iostream>
#include "OnePen.h"

void test01()
{
	OnePen op;
	op.setNodeNum(4);
	op.setNodeJoin(1, 2);
	op.setNodeJoin(1, 3);
	op.setNodeJoin(2, 3);
	op.setNodeJoin(2, 4);
	op.printTable();
	op.drawLine();
}

void test02()
{
	OnePen op;
	op.setNodeNum(5);
	op.setNodeJoin(1, 4);
	op.setNodeJoin(1, 5);
	op.setNodeJoin(2, 4);
	op.setNodeJoin(2, 5);
	op.setNodeJoin(3, 4);
	op.setNodeJoin(3, 5);
	op.setNodeJoin(4, 5);
	op.printTable();
	op.drawLine();
}

int main()
{
	test02();
	system("pause");
	return 0;
}

• OnePen.h

#pragma once
#include <iostream>
#include <vector>

class OnePen
{
private:
	struct node				// 节点
	{
		int data;			// 数据域
		bool flag;			// 标记（1已使用0未使用）
		node* next;			// 下一个
	};

	node* nodeArray;		// 节点数组
	int nodeNum;			// 节点数量
	std::vector<int> path;	// 路径

	bool checkAlone();
	bool sign(int p1, int p2, int flag);
	bool endCheck();
	int draw(int p);
public:
	OnePen();
	void setNodeNum(int num);
	void setNodeJoin(int begin, int end);
	void printTable();
	void drawLine();
};

• OnePen.cpp

#include "OnePen.h"

// 构造函数，初始化成员变量
OnePen::OnePen()
{
	this->nodeNum = 0;
	this->nodeArray = NULL;
}

// 设置节点数量，并生成初始数组
void OnePen::setNodeNum(int num)
{
	if (num <= 1)
	{
		std::cout << "节点数必须大于 1。" << std::endl;
	}
	else
	{
		this->nodeNum = num;
		this->nodeArray = new node[num];

		for (int i = 0; i < num; i++)
		{
			this->nodeArray[i].data = i;
			this->nodeArray[i].flag = false;
			this->nodeArray[i].next = NULL;
		}
	}
}

// 连接节点
void OnePen::setNodeJoin(int begin, int end)
{
	// 首尾不能相同
	if (begin == end)
	{
		std::cout << "首尾节点不能相同，请重新确认！";
		std::cout <<"（Error: .setNodeJoin(" << begin << "," << end << ");）" << std::endl;
		return;
	}
	
	// 其中一节点不存在
	bool beginExist = false, endExist = false;
	for (int i = 0; i < this->nodeNum; i++)
	{
		// 数据存储节点是从0开始，但是从用户角度节点是从1开始，所以需要-1
		if (this->nodeArray[i].data == begin - 1)
			beginExist = true;
		if (this->nodeArray[i].data == end - 1)
			endExist = true;
	}
	if (!beginExist || !endExist)
	{
		std::cout << "节点不存在，请重新确认！";
		std::cout << "（Error: .setNodeJoin(" << begin << "," << end << ");）" << std::endl;
		return;
	}

	// 找到 begin 节点的最后一个邻接节点，然后插入新的邻接节点
	node* beginNode = &this->nodeArray[begin - 1];	// begin节点
	while (NULL != beginNode->next)
	{
		if (beginNode->next->data == end - 1)
		{
			// 已存在从 begin -> end 的路线
			break;
		}
		beginNode = beginNode->next;
	}
	if (beginNode->next == NULL)
	{
		node* temp = new node;
		temp->data = end - 1;
		temp->flag = 0;
		temp->next = NULL;
		beginNode->next = temp;
	}
	
	// 找到 end 节点的最后一个邻接节点，然后插入新的邻接节点
	node* endNode = &this->nodeArray[end - 1];		// end节点
	while (NULL != endNode->next)
	{
		if (endNode->next->data == begin - 1)
		{
			// 已存在从 end -> begin 的路线
			break;
		}
		endNode = endNode->next;
	}
	if (endNode->next == NULL)
	{
		node* temp = new node;
		temp->data = begin - 1;
		temp->flag = 0;
		temp->next = NULL;
		endNode->next = temp;
	}
}

// 输出邻接表
void OnePen::printTable()
{
	std::cout << "当前邻接表为：" << std::endl;
	std::cout << "-----------------------------" << std::endl;
	for (int i = 0; i < this->nodeNum; i++)
	{
		std::cout << this->nodeArray[i].data + 1 << " | ";
		node* temp = this->nodeArray[i].next;
		while (temp != NULL)
		{
			std::cout << " ->" << temp->data + 1;
			temp = temp->next;
		}
		std::cout << std::endl;
	}
	std::cout << "-----------------------------\n" << std::endl;
}

// 检查是否存在独立的点（即出度和入度皆为0）
bool OnePen::checkAlone()
{
	for (int i = 0; i < this->nodeNum; i++)
	{
		if (this->nodeArray[i].next == NULL)
		{
			return true;
		}
	}
	return false;
}

// 设置标记（p1->p2 的 flag 设置为 flag）
bool OnePen::sign(int p1, int p2, int flag)
{
	node* it = this->nodeArray[p1].next;
	while (it != NULL)
	{
		if (it->data == p2)
		{
			it->flag = flag;
			return true;
		}
		it = it->next;
	}
	return false;
}

// 最终检查（邻接表的全部flag都为1即返回true）
bool OnePen::endCheck()
{
	node* temp;
	for (int i = 0; i < this->nodeNum; i++)
	{
		temp = this->nodeArray[i].next;
		while (NULL != temp)
		{
			if (temp->flag == 0)
			{
				return false;
			}
			temp = temp->next;
		}
	}
	return true;
}

// 开始画线
void OnePen::drawLine()
{
	// 检查是否存在独立的点
	if (this->checkAlone())
	{
		std::cout << "- 单独的节点：\n\n>>> ";
		for (int i = 0; i < this->nodeNum; i++)
		{
			if (this->nodeArray[i].next == NULL)
			{
				std::cout << this->nodeArray[i].data << "\t";
			}
		}
		std::cout << "\n\n- 请将全部节点连接！\n" << std::endl;
		return;
	}

	// 统计有多少种方法
	int count = 1;
	// 从每个节点为初始节点依次走一次
	for (int i = 0; i < this->nodeNum; i++)
	{
		// 将全部标签置0
		for (int j = 0; j < this->nodeNum; j++)
		{
			node* t = this->nodeArray[j].next;
			while (t != NULL)
			{
				t->flag = 0;
				t = t->next;
			}
		}

		// 将路径清空
		this->path.clear();

		// 开始画线draw(i)，其中i为初始节点，返回结果为是否走得通
		if (this->draw(i))
		{
			std::cout << "-----------------------------" << std::endl;
			std::cout << ">>> 第 " << count << " 种解法：\n>>> ";
			count++;
			for (int i = 0; i < this->path.size(); i++)
			{
				if (i == 0)
					std::cout << this->path[i];
				else
					std::cout << " ->" << this->path[i];
			}
			std::cout << "\n" << std::endl;
		}
	}
}

// 以point节点为开始节点走下一步
int OnePen::draw(int point)
{
	// 当前节点添加到路径（由于存储和显示不同，所以+1）
	this->path.push_back(point + 1);

	// 完成（到该点已经全部路线都走完了就逐层返回1）
	if (this->endCheck())
	{
		return 1;
	}

	node* past = new node;					// 走过节点列表（已经走过并且走不通）
	node* last = past;						// 走过节点列表 的最后一个节点（方便添加新的节点）
	int peerNode = -1;						// 目标节点（将要走的节点，初始化为不可能的-1）

	node* it = this->nodeArray[point].next;	// 当前节点的第一个邻接点
	// 找到下一个要走的节点，并且标记
	while (it != NULL)
	{
		if (it->flag == 0)			// 尚未走过的目标节点
		{
			peerNode = it->data;	// 记录目标节点
			it->flag = 1;			// 标记目标节点
			past->data = peerNode;	// 目标节点加入past列表
			past->next = NULL;
			break;
		}
		it = it->next;
	}

	// 此路不通（遍历完当前节点的所有邻接点都没找到flag=0的节点即无路可走了）
	if (it == NULL)
	{
		return 0;
	}

	// 将目标节点到当前节点的线标记
	this->sign(peerNode, point, 1);

	// 开始递归，如果递归结果返回0（即此路不通）开始进入循环找新的目标节点
	while (!this->draw(peerNode))
	{
		// 进入循环证明当前past列表的最新元素走不通，移除
		this->path.pop_back();

		// 1. 将刚刚走过的标记取消（让其他节点可以走）
		this->sign(point, peerNode, 0);
		this->sign(peerNode, point, 0);

		// 2. 找到一个节点需要即不在past列表里，并且flag为0
		it = this->nodeArray[point].next;
		while (it != NULL)
		{
			if (it->flag == 0)
			{
				bool b = true; // 检查这个节点是否存在past列表（1这个节点能走，0这个节点不能走）

				// 遍历走过列表
				node* ps = past;
				while (ps != NULL)
				{
					// 如果当前节点存在走过列表里面，这个节点不能走
					if (it->data == ps->data)
					{
						b = false;
						break;
					}
					ps = ps->next;
				}

				// 找到目标节点
				if (b)
				{
					peerNode = it->data;

					// 添加到走过列表
					node* past2 = new node;
					past2->data = peerNode;
					past2->next = NULL;
					last->next = past2;		// 添加到past列表的最后
					last = past2;			// last指向past列表的最后元素

					// 标记（当前节点到目标节点的路线已使用）
					this->sign(point, peerNode, 1);
					this->sign(peerNode, point, 1);

					// 退出循环
					break;
				}
			}

			it = it->next;
		}
		
		// 3. 遍历完邻接点也没找到可用的节点，没有可以走的路线了，此路不通
		if (it == NULL)
		{
			return 0;
		}
	}
}