练习图的遍历、回溯
网站建设公司,为您提供网站建设,网站制作,网页设计及定制网站建设服务,专注于企业网站建设,高端网页制作,对成都OPP胶袋等多个行业拥有丰富的网站建设经验的网站建设公司。专业网站设计,网站优化推广哪家好,专业seo优化排名优化,H5建站,响应式网站。
新建一个OnePen类；
使用setNodeNum()方法设置节点数量；
使用setNodeJoin()设置节点连线；
执行drawLine()方法即可得出该图的一笔画路线；
#include#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;
} #pragma once
#include#includeclass OnePen
{private:
struct node // 节点
{int data; // 数据域
bool flag; // 标记（1已使用0未使用）
node* next; // 下一个
};
node* nodeArray; // 节点数组
int nodeNum; // 节点数量
std::vectorpath; // 路径
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();
}; #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;
}
}
}测试（上面的main.cpp的test02函数）
执行结果
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
