--------- node.h ------------------//定义节点类
#include<string>
#include<vector>
using namespace std;
class node
{
public:
node(int c,const string _name):cp(c),name(_name){}
string name; //结点名称
int cp; //结点标号
};
----------- sort.h ---------------------//寻找哈密尔顿回路的算法部分
#include<iostream>
#include<string>
#include<vector>
#include"node.h"
using namespace std;
vector<node> v_sort; //记录当前搜索时结点的连接状况
int N; //结点总数
vector<string> in_name; //结点名称
vector<vector<bool> > link_state; //结点的初始连接状况
vector<vector<bool> > clink; //结点当前连接状况(用于搜索)
//用于搜索的函数,由sort()调用,搜索结果保存在v_sort里
int node_sort()
{
int count=v_sort.back().cp; //v_sort栈顶结点的标号
if(v_sort.size()==N && link_state[count][0]==true)
return 1; //当成功找到一回路时返回 1
//通过查看clink进行搜索
for(int i=0;i<N;i++)
{
//发现另一结点M可与该结点相连
if(clink[count][i]==true)
{
bool in_stack=false; //标示M是否已在v_sort里
for(int j=0;j<v_sort.size();j++)
if(v_sort[j].name==in_name[i])
in_stack=true; //M已在v_sort里
if(in_stack==false)
{
//压入M结点
node tmp(i,in_name[i]);
v_sort.push_back(tmp);
//修改clink,堵住已走的路
clink[i][count]=false;
clink[count][i]=false;
return 0;
}
}
}
v_sort.pop_back(); //当找不到路时弹出该结点
clink[count]=link_state[count]; //恢复弹出结点的初始连接状态
return 0;
if(v_sort.size()==0)
return -1; //搜索失败,此时v_sort为空,返回-1
}
//sort函数由用户调用,依次传入结点数量,名称,初始连接状况;输出排好的结点名
bool sort(int n,const vector<string> _in_name,const vector<vector<bool> > _link_state,vector<string>& out_name)
{
//初始化全局变量
N=n;
in_name=_in_name;
link_state=_link_state;
clink=link_state;
v_sort.clear();
//先压入第一个结点
node first(0,in_name[0]);
v_sort.push_back(first);
while(1)
{
int r=node_sort();
if(r==1)
{
for(int i=0;i<n;i++)
out_name.push_back(v_sort[i].name);//找到回路就初始化out_name
return true;
}
if(r==-1)
return false; //未找到
}
}
------------- main.cpp ----------------//这个是调用部分,没有注释,有点乱,不过不是主要的
#include<iostream>
#include<string>
#include<vector>
#include"sort.h"
#include<cstdlib>
using namespace std;
void main()
{
cout<<endl<<"*************寻找哈密尔顿回路程序***************/n";
string is_continue="y";
while(is_continue=="y"||is_continue=="Y" )
{
int np;
string inN;
vector<string> in_name;
bool judge=true;
cout<<"/n 请依次输入各节点名称,以空格隔开:";
while(1)
{
do{
cin>>inN;
judge=true;
for(int i=0;i<in_name.size();i++)
{
if(inN==in_name[i])
{
cout<<"/n!节点名称不能重复,请重新输入各节点名称(先空一格):";
judge=false;
cin.ignore(1000,'/n');
in_name.assign(0,"");
break;
}
}
if(judge==true)
in_name.push_back(inN);
}while(cin.get()!='/n');
if(in_name.size()>=3)
break;
cout<<"/n!节点数必需大于或等于3,请重新输入:";
in_name.assign(0,"");
}
np=in_name.size();
vector<bool> _link_state(np);
vector<vector<bool> > link_state;
string in_link;
cout<<"/n请依次输入该节点与所有节点的连接情况,以空格隔开/n ";
for(int i=0;i<np;i++)
cout<<in_name[i]<<" ";
cout<<"/n";
bool input_again=false;
for(i=0;i<np;i++)
{
do{
input_again=false;
cout<<" "<<in_name[i]<<":";
for(int k=0;k<np;k++)
{
cin>>in_link;
if(in_link!="0" && in_link!="1")
{
cout<<"/n !!只能输入'0'/'1',请重新输入该节点连接情况:/n";
input_again=true;
cin.ignore(1000,'/n');
break;
}
else if(k==i && in_link=="1")
{
cout<<"/n !!这里节点不能与自身相连,请重新输入该节点连接情况:/n";
input_again=true;
cin.ignore(1000,'/n');
break;
}
in_link=="0"? _link_state[k]=false:_link_state[k]=true;
}
}while(input_again==true);
link_state.push_back(_link_state);
}
vector<string> out_name;
if(sort(np,in_name,link_state,out_name)==false)
cout<<"/n 无哈密尔顿回路 /n";
else
{
cout<<"/n 找到一条哈密尔顿回路: /n";
for(i=0;i<out_name.size();i++)
cout<<out_name[i]<<"---";
cout<<out_name[0];
}
cout<<"/n/n是否继续?(y/n):";
cin>>is_continue;
while(is_continue!="Y" && is_continue!="y" && is_continue!="N" && is_continue!="n")
{
cout<<"/n只能输入'y'/'n',请重新选择(y/n):";
cin>>is_continue;
}
}
cout<<"/n欢迎使用/n";
system("PAUSE");
}
分享到:
相关推荐
哈工大算法实验三,搜索算法(哈密顿环问题)求解哈密顿环 1.实现基于树的深度优先搜索算法,求解哈密顿环问题 2.实现哈密顿环的爬山法 3.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析...
四正则连环图的哈密顿图性质研究及其判定的多项式算法,宁安琪,宁宣熙,在本文中定义了一般四正则连环图,并讨论了它的哈密顿图性质。研究表明,并非在全部四正则连环图中都存在哈密顿圈。研究了几种存
1. 通过贪心算法对可以回到起点的环游解——哈密顿回路 进行了优化。当棋盘规模小于12时,能够迅速给出任意一个节点的一条哈密顿解 2. 若不要求回到起点最大规模可达60 3. 可以自定义是否回到起点,棋盘规模以及是否...
《C算法(第2卷)(图算法)(第3版)(中文版)》所讨论的图算法,都是实际中解决图问题的最重要的已知方法。《C算法(第2卷)(图算法)(第3版)(中文版)》的主要宗旨是让越来越多需要了解这些算法的人的能够掌握这些方法及基本...
针对具有哈密顿环的互连网络(也称做哈密顿网络),利用分治回环思想,提出了一种新的基于PMC故障模型自适应的诊断算法。其核心思想是,对哈密顿网络进行序列划分,然后对得到的每个01序列的结节进行回环诊断,最后...
24.2 有向无环图中的单源最短路径问题 24.3 Dijkstra算法 24.4 差分约束和最短路径 24.5 最短路径性质的证明 思考题 本章注记 第25章 所有结点对的最短路径问题 25.1 最短路径和矩阵乘法 25.2...
马的Hamilton周游路线问题,8*8 的国际象棋棋盘上的一只马,恰好走过除起点外的其它63 个位置各一次,最后...对于给定的m*n 的国际象棋棋盘,m和n均为大于5 的偶数,且|m-n|≤2,该算法找出一条马的Hamilton周游路线。-
有向最短哈密尔顿路问题的DNA算法是一份整理发布的食品资料文档,只为你能够轻松获取有向最短...该文档为有向最短哈密尔顿路问题的DNA算法,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
当前已支持算法:快速排序、插入排序、堆排序、归并排序、取最大、取最小、向下...包含算法:dijkstra、floyd、SPFA、kruskal、prim、tarjan强连通分量、遍历、求哈密顿环、匈牙利算法求二分图最大匹配、连通性判断)
leetcode oj 调试 Algorithm-Punch 每日打卡,记录自己算法与数据结构的学习心得 每个人可以用自己名字拼音首字母作为分支名记录自己的学习笔记 学习资料 ...哈密顿图 二分图 最小环 图的着色 License MIT
第1章介绍一维、二维的非线性混沌映射,第2章介绍时间序列分析,第3章介绍平面自治系统,第4章介绍非线性哈密顿系统,第5章介绍非线性耗散系统,第6章介绍非线性动力学系统,第7章介绍混沌控制,第8章介绍混沌同步性...
包含算法:dijkstra、floyd、SPFA、kruskal、prim、tarjan强连通分量、遍历、求哈密顿环、匈牙利算法求二分图最大匹配、连通性判断) 另外给喜爱算法的人推荐一本书:刘汝佳的《算法竞赛入门经典》,pan.baidu....
求解单旅行商问题的智能算法,蚁群算法。输入城市间赋权向量(城市间路程),即可输出经过所有城市且总路程最短的最小哈密顿环。
有理Calogero模型(A n -1型并且在除去质心之后)的球形缩减被视为最大超积分量子系统,该系统描述了在(n -2)球面上的... 它们通过将在所有Weyl反射下的子空间不变和反不变分类,从Dunkl变形角动量中的多项式环产生。
哈密顿环的存在 哈密顿步行的存在 查找简单路径数 寻找最短的哈密顿周期 哈密顿循环数 简单循环数 最短的汉密尔顿步行 子集子集(3 ^ n) 数据结构 AVL树 大整数 二进制堆 二项式堆 不相交集 Fenwick树...