波波老师麻烦您了，欧拉回路问题
来源：10-4 求解欧拉回路的三种算法
慕仰0554757
2020-10-28
void dfs(int i) //这个点深度优先遍历过程寻找欧拉路
{
int j;
for (j = 1; j <= n; j++)
if (g[i][j] == 1) //从任意一个与它相连的点出发
{
g[j][i] = g[i][j] = 0;
dfs(j);
}
circuit[++circuitpos] = i; //记录下路径
}
问题1：我找了很多别人的欧拉回路算法，就是dfs这样的。解决不了上图的欧拉回路问题，这上面代码（网络上大部分都是这样的dfs）只是在某些图上可以找出欧拉回路，是不是错误代码？
void dfs(int i){
for(int j=1;j<=n;j++){
if(mapp[i][j]==1){
mapp[i][j]=mapp[j][i]=0; //从i点出发
num[++c]=i;
if (c==m) { //遍历所有边
pr();
}
else dfs(j);
mapp[i][j]=mapp[j][i]=1; //回溯
--c;
}
}
}
我改进成这样对不对？
写回答
1回答
-
我刚刚使用这个测试用例测试了一下这个课程 10-6 的代码，没有问题：https://git.imooc.com/coding-370/Play-with-Graph-Theory-Algorithm/src/master/10-Euler-Loop-and-Euler-Path/06-Hierholzer-Algorithm/src/EulerLoop.java
如果你使用这个课程的代码测试这个测试用例有问题，请确认自己的图文件是正确的。因为你你的图中的顶点标号是从 1 开始的，但实际上我们的代码中的顶点是从 0 开始的。我的测试文件内容如下：
13 16 8 9 9 1 1 7 7 8 0 1 1 2 2 3 3 0 2 10 10 11 11 12 12 2 3 6 6 5 5 4 4 3
如果你在网上找到的代码针对这个测试用例结果是错误的，那肯定是错误的。
因为我没有你的这个程序的完整代码和相应的思路，我也不能确定是否是正确的，你需要自己进行测试。
加油！：）
112020-10-28
相似问题