c++ - 图论 - 从顶点 A 开始，沿两个方向遍历所有路径，以最短路线再次到达 A

Question

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

Find the path in a graph where you start from vertex A, go through all edges exactly two times per edge in BOTH directions (one time in one direction, second time in the opposite) and end up in vertex A again as a last step.

如果有人给我一些关于如何调用这个问题的提示(因为它听起来像一个众所周知的问题)以及它的解决方案的一些指导，我会很高兴。

Answer 1

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

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

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

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

如果你想访问一个循环中的所有边缘(没有在路径中间回溯)那么你正在寻找欧拉回路/巡回赛并且可以使用 Hierholzer 的 1873 算法:

Wikipedia

• Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
• As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.