java - 在图中使用循环进行寻路（使用每条边一次）

Question

我想在图中搜索一些路径。图表有循环，它们经常发生。

带回关于画房子的老谜语，不提笔，画同一边2次。

  ^
 / \
/ _ \
|\ /|
| x |
|/_\|

它有 5 个顶点和 8 个边。假设我想检查是否可以在给定起始顶点的情况下在不“举起笔”的情况下绘制这样的图形。请注意，我可以（并且可能需要）处理具有不同地图状态的相同顶点（是否使用周围的边缘？）几次。在运行 BFS/DFS 时，我是否必须为每个节点制作整个边缘使用数组的副本？有什么简单的方法可以做到这一点吗？

Answer 1

对于 DFS，您只需要在边缘访问过标志。你不需要复制它，只需在调用后重置它。

伪代码：

for each node
  for each edge
    edge.visited = false
  dfs(node)

dfs(node)
  // do something with node?
  // perhaps check numberOfEdges == visited.size() to see if we're done
  for each edge in node
    if (!edge.visited)
      edge.visited = true
      dfs(edge.other(node))
      edge.visited = false

Answer 2

假设我想检查是否可以在给定起始顶点的情况下在不“举起笔”的情况下绘制这样的图形。

如果图形没有连接，则无法绘制。否则，如果图没有奇数度的顶点，则无论您从哪个顶点开始，都有可能。如果它有两个这样的顶点，当且仅当给定顶点的度数为奇数时才有可能。如果它有两个以上奇数度的顶点，那是不可能的。

我想在图中搜索一些路径。

如果绘图是可能的（见上文），只要剩余的边是连接的，任何路径都可以。