波波老师这是我的哈密顿回路c++源程序，你看看对不对？
来源：9-3 实现哈密尔顿回路的算法
慕仰0554757
2020-10-27
//旅行商问题之一
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
int g[101][101],n,m,length,x,start;
bool v1[101];
int ans[101],num[101];
void print() //打印结果
{ int i;
for (i = 1; i <= length; i++)
cout << ' ' << ans[i];
cout << endl;
}
bool allvisited(){ //全部被访问？yes： no
for(int i=1;i<=n;i++)
if (v1[i]==0) return false;
return true;
}
bool dfs(int last,int i)//last是i顶点的父亲结点，从i顶点开始dfs
{
v1[i] = true; //访问i顶点
ans[++length] = i; //保存i到数组
for (int j = 1; j <= num[i]; j++) {
if (g[i][j]==start&&allvisited()) //**g[i][]数组，表示出i出发的点**
{
ans[++length] = g[i][j];
print();
length--;
}
if (!v1[g[i][j]])
if (dfs(i,g[i][j])) return true;
}
length--;
v1[i] = false;
return false;
}
int main(){
memset(v1,false,sizeof(v1));
cin>>n>>m; //n个结点m条边
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
g[x][++num[x]]=y; //**从x出发的边放进二维数组，共num[x]条**
g[y][++num[y]]=x;
}
start=1;
dfs(1,start); //从一号点开始深度优先搜索
return 0;
}
/*第一个样例
4 5
1 2
1 3
1 4
2 3
2 4
两条哈密尔顿回路
1 3 2 4 1
1 4 2 3 1
哈密尔顿12面体的样例 20个点，30条边
20 30
1 2
1 5
1 14
2 3
2 12
3 10
3 4
4 5
4 8
5 6
6 7
6 15
7 8
7 17
8 9
9 10
9 18
10 11
11 12
11 19
12 13
13 14
13 20
14 15
15 16
16 17
16 20
17 18
18 19
19 20
¹þÃܶû¶Ù»Ø·
1 2 3 10 9 8 4 5 6 7 17 18 19 11 12 13 20 16 15 14 1
1 2 3 10 9 18 17 7 8 4 5 6 15 16 20 19 11 12 13 14 1
1 2 3 10 9 18 17 16 20 19 11 12 13 14 15 6 7 8 4 5 1
1 2 3 10 9 18 19 11 12 13 20 16 17 7 8 4 5 6 15 14 1
1 2 3 10 11 12 13 14 15 6 7 17 16 20 19 18 9 8 4 5 1
1 2 3 10 11 12 13 20 19 18 9 8 4 5 6 7 17 16 15 14 1
1 2 3 4 5 6 7 8 9 10 11 12 13 20 19 18 17 16 15 14 1
1 2 3 4 5 6 15 16 20 19 18 17 7 8 9 10 11 12 13 14 1
1 2 3 4 8 7 17 16 20 19 18 9 10 11 12 13 14 15 6 5 1
1 2 3 4 8 9 10 11 12 13 14 15 16 20 19 18 17 7 6 5 1
1 2 12 11 10 3 4 5 6 15 16 17 7 8 9 18 19 20 13 14 1
1 2 12 11 10 3 4 8 9 18 19 20 13 14 15 16 17 7 6 5 1
1 2 12 11 19 18 9 10 3 4 8 7 17 16 20 13 14 15 6 5 1
1 2 12 11 19 18 17 7 8 9 10 3 4 5 6 15 16 20 13 14 1
1 2 12 11 19 18 17 16 20 13 14 15 6 7 8 9 10 3 4 5 1
1 2 12 11 19 20 13 14 15 16 17 18 9 10 3 4 8 7 6 5 1
1 2 12 13 14 15 6 7 8 9 18 17 16 20 19 11 10 3 4 5 1
1 2 12 13 14 15 16 20 19 11 10 3 4 8 9 18 17 7 6 5 1
1 2 12 13 20 16 17 7 8 9 18 19 11 10 3 4 5 6 15 14 1
1 2 12 13 20 19 11 10 3 4 5 6 7 8 9 18 17 16 15 14 1
1 5 4 3 2 12 11 10 9 8 7 6 15 16 17 18 19 20 13 14 1
1 5 4 3 2 12 13 20 16 17 18 19 11 10 9 8 7 6 15 14 1
1 5 4 3 10 9 8 7 6 15 14 13 20 16 17 18 19 11 12 2 1
1 5 4 3 10 11 19 20 16 17 18 9 8 7 6 15 14 13 12 2 1
1 5 4 8 7 6 15 14 13 12 11 19 20 16 17 18 9 10 3 2 1
1 5 4 8 7 6 15 16 17 18 9 10 3 2 12 11 19 20 13 14 1
1 5 4 8 9 10 3 2 12 11 19 18 17 7 6 15 16 20 13 14 1
1 5 4 8 9 18 17 7 6 15 16 20 19 11 10 3 2 12 13 14 1
1 5 4 8 9 18 19 11 10 3 2 12 13 20 16 17 7 6 15 14 1
1 5 4 8 9 18 19 20 16 17 7 6 15 14 13 12 11 10 3 2 1
1 5 6 7 8 4 3 2 12 13 20 19 11 10 9 18 17 16 15 14 1
1 5 6 7 8 4 3 10 9 18 17 16 15 14 13 20 19 11 12 2 1
1 5 6 7 17 16 15 14 13 20 19 18 9 8 4 3 10 11 12 2 1
1 5 6 7 17 18 9 8 4 3 10 11 19 20 16 15 14 13 12 2 1
1 5 6 7 17 18 19 11 10 9 8 4 3 2 12 13 20 16 15 14 1
1 5 6 7 17 18 19 20 16 15 14 13 12 11 10 9 8 4 3 2 1
1 5 6 15 14 13 12 11 10 9 18 19 20 16 17 7 8 4 3 2 1
1 5 6 15 14 13 20 16 17 7 8 4 3 10 9 18 19 11 12 2 1
1 5 6 15 16 17 7 8 4 3 2 12 11 10 9 18 19 20 13 14 1
1 5 6 15 16 20 19 11 10 9 18 17 7 8 4 3 2 12 13 14 1
1 14 13 12 2 3 10 11 19 20 16 15 6 7 17 18 9 8 4 5 1
1 14 13 12 2 3 4 8 7 17 18 9 10 11 19 20 16 15 6 5 1
1 14 13 12 11 10 9 8 7 17 18 19 20 16 15 6 5 4 3 2 1
1 14 13 12 11 19 20 16 15 6 5 4 8 7 17 18 9 10 3 2 1
1 14 13 20 16 15 6 5 4 3 10 9 8 7 17 18 19 11 12 2 1
1 14 13 20 16 15 6 7 17 18 19 11 12 2 3 10 9 8 4 5 1
1 14 13 20 19 11 12 2 3 10 9 18 17 16 15 6 7 8 4 5 1
1 14 13 20 19 18 9 8 7 17 16 15 6 5 4 3 10 11 12 2 1
1 14 13 20 19 18 9 10 11 12 2 3 4 8 7 17 16 15 6 5 1
1 14 13 20 19 18 17 16 15 6 7 8 9 10 11 12 2 3 4 5 1
1 14 15 6 5 4 3 10 11 19 18 9 8 7 17 16 20 13 12 2 1
1 14 15 6 5 4 8 7 17 16 20 13 12 11 19 18 9 10 3 2 1
1 14 15 6 7 8 9 10 11 19 18 17 16 20 13 12 2 3 4 5 1
1 14 15 6 7 17 16 20 13 12 2 3 10 11 19 18 9 8 4 5 1
1 14 15 16 17 7 6 5 4 8 9 18 19 20 13 12 11 10 3 2 1
1 14 15 16 17 18 9 8 7 6 5 4 3 10 11 19 20 13 12 2 1
1 14 15 16 17 18 9 10 11 19 20 13 12 2 3 4 8 7 6 5 1
1 14 15 16 17 18 19 20 13 12 11 10 9 8 7 6 5 4 3 2 1
1 14 15 16 20 13 12 2 3 4 8 9 10 11 19 18 17 7 6 5 1
1 14 15 16 20 13 12 11 19 18 17 7 6 5 4 8 9 10 3 2 1
*/
1.问题一：这个程序对不对？我检查过是对的，您给看看？
2.为什么你上课只会打印出一条答案？
1回答
-
liuyubobobo
2020-10-28
1
目测没有问题。在 Leetcode 上有哈密顿回路（或者路径）的问题，你可以使用你的逻辑，试一下能否通过这些问题。比如这里：https://leetcode.com/problems/find-the-shortest-superstring/
2
因为在我的代码中，一旦找到一条回路，直接就返回了。
继续加油！：）
00
相似问题