图论 - 从顶点 A 开始，经过两个方向的所有路径，最后以最短路线再次到达 A

Question

我试图找到这个问题的名称，但不知道如何搜索它。问题如下：

找到图中的路径，从顶点 A 开始，在两个方向上每条边恰好经过所有边两次（一次在一个方向，第二次在相反方向），最后一步再次到达顶点 A。

如果有人给我一些关于如何称呼这个问题的提示（因为它听起来像是一个众所周知的问题），并且可能提供一些解决方案的指导，我会很高兴。

Answer 1

如果您只想在每个方向上遍历连通图的每条边一次，那么您可以使用深度优先搜索：

• 选择任意顶点作为起点。
• 从当前顶点选取任何未访问过的入射边。
  • 将该边缘标记为已访问。
  • 如果边的另一端是未访问的顶点，则移动到该新顶点，将其标记为已访问，然后从该新顶点重复该过程。
  • 如果边的另一端是访问过的顶点，则立即回溯（第二次遍历该边，但方向相反）并继续处理连接到当前顶点的边。
  • 一旦访问了当前顶点的所有关联边，则沿着最初将您带到该顶点的边回溯，并返回处理连接到前一个顶点的边。

一旦 DFS 完成，您将在每个方向上恰好遍历每条边一次。

您同样可以使用广度优先搜索而不是深度优先搜索。

如果您想访问一个循环中的所有边缘（不在路径中间回溯），那么您正在寻找欧拉电路/旅行，并且可以使用 Hierholzer 的 1873 算法：

维基百科

• 选择任何起始顶点 v，并沿着从该顶点开始的边轨迹直到返回到 v。不可能卡在除 v 之外的任何顶点，因为所有顶点的偶数度确保了当轨迹进入另一个顶点时w 必须有一条未使用的边离开 w。这样形成的游览是封闭游览，但可能不会覆盖初始图的所有顶点和边。
• 只要存在属于当前游览的顶点 u，但其相邻边不属于该游览，则从 u 开始另一条路径，沿着未使用的边，直到返回到 u，并将以此方式形成的游览加入到前一个路径中旅游。