实现Hierholzer就while循环前stack第一次压栈的疑问

Question

老师，我的疑问写在了上图中，你看下哈:)

Answer 1

liuyubobobo 2021-11-11 04:19:34

欧拉回路指每条边必须走且仅走一次。点重复是正常的。比如 一个图是 0-1 之间四条路。那么对应的欧拉回路是：0-1-0-1-0。

或者我没有理解你的问题，你认为问题是什么，用一个具体的测试用例来说明？

继续加油！：）

• 提问者 甲骨文_0001 #1

  0
  /    \
  1  -  2
  
  老师，以上图为例，0, 1, 2组成了三角形,是欧拉回路. 然后按照视频中的代码逻辑来走:
  int curv=0
  stack.push(curv) // 此时栈中 [0]
  
  while( !stack.empty() ){
      if(g.degree(curv)!= 0){
          stack.push(curv) // 将当前curv压入栈中
          int w = g.adj(curv).iterator().next(); // 遍历curv相仿的下一个顶点
          g.removeEdge(curv, w); // curv, w间的边删除
          curv=w; // 将邻居w点赋予为curv
      }else{
          res.add(curv); // 结果数组中添加curv
          curv = stack.pop(); // curv赋为接下来的栈顶顶点
      }
  }
  
  在while循环中:
  1: curv=0, stack:[0, 0]
  2: w=1, 删除0-1
     0
      \
    1 - 2
  3: curv = 1, stack: [0, 0, 1]
  4: w = 2, 删除 1 - 2
     0
      \
  1     2
  5: curv = 2, stack: [0, 0, 1, 2]
  6: w = 0, 删除 2 - 0
    0
  
  1    2
  
  7: curv = 0 此时 g.degree(w) == 0
  
  8: res: [0], curv = 2
  9: res: [0, 2], curv = 1
  10: res: [0, 2, 1], curv = 0
  11: res: [0, 2, 1, 0], curv = 0
  12: res:[0, 2, 1, 0, 0]
  
  ---------------
  我是前端程序员:), 就是最终结果数组中 0这个点会出现 3次，我是看是java的逻辑自己模拟出来的哈，上述是我的一个思路过程，所以我认为之所以会出现3个0，是因为while前stack先把curv=0压入了一遍:), 不知道我说的对不对，老师你看看哈

• 提问者 甲骨文_0001 #2

  老师 要用PC电脑查看我的回复 手机屏幕小 回复里的字都挤到一起了😅

• liuyubobobo 回复 提问者 甲骨文_0001 #3

  我明白你的问题了。你的模拟最后一部分有误。可能因为你没有写 stack 导致的。在 while 的 else 部分里，并非是把最后的 curv 添加到 res 以后，再把 stack 里的所有节点都放到 res 里。stack 的最后一个节点 pop 出来以后，没有放到 res 里。（else 内的逻辑是先 res.add， 再 stack.pop）。res 里的元素数和 stack 是一致的，而非多一个。如果还想不明白，请尝试运行这个程序试试看？继续加油！：）