遍历图中所有边的算法

Question

作为个人的复活节项目，我正在尝试在工作中实现一些基于模型的测试。我已经在Python中实现了一个图形，我需要遍历图形的所有边缘/执行所有过渡，至少一次。多次遍历一条边并不重要，但我需要从同一节点开始和结束，并得到一系列的边缘/过渡。

简单算法 > 最短序列。

我已经查找了许多算法，但我找不到一个/一组适合我的算法。如果有人能指导我方向或给我一些做这件事情的提示，那将会很棒。

我的图形实现看起来像这样:

graph = {
    A : {'IDLE': 't8', 'B': 't2', 'C': 't4'},
    B : {'A': 't3', 'C': 't4', 'IDLE': 't6'},
    C : {'A': 't5', 'IDLE': 't7', 'B': 't2'},
    IDLE : {'A': 't1'}
}

- kristus

---

你的图看起来是有向的。你只能沿着箭头遍历吗？ - Oliver Charlesworth

这就是旅行商问题，不是吗。如果您找到解决方案，请务必让全世界知道。 - Daniel Roseman

我们可以假设你的图是强连通的吗？ - Mark Byers

@DanielRoseman：实际上这是欧拉回路。TSP处理的是访问所有节点，而不是所有边。 - Avaris

@Avaris：实际上这不是欧拉回路，因为你可以多次访问边缘。OP的要求是每条边至少被访问一次。 - Mark Byers

Answer 1

方法1

您可以将图G转换为一个新的图G'，其中G中的每条边都变成了G'中的一个节点。如果在G中存在一些A、B和C，使得"A -> t1 -> B -> t2 -> C"是可能的，则在G'中从t1到t2创建一条边。

然后您需要在G'中找到一个路径覆盖。

方法2

• 您的初始位置P是某个节点P0（例如空闲）。
• 对于每条从A到B的边T，找到任何从P到A的路线，然后使用T前往B。更新P为B。
• 最后找到任何从P返回到P0的路线。

- Mark Byers

---

谢谢，我会研究一下。G'解决方案听起来非常有趣。 - kristus

Answer 2

这个问题不同于旅行商问题(TSP)，而是被称为中国邮递员问题(CPP)。最大的区别在于TSP想要访问所有节点(城市)，而CPP想要访问所有边缘(街道)。

针对此问题的完美教程可以在这里找到: https://www.datacamp.com/community/tutorials/networkx-python-graph-tutorial

- Yannick Mister

Answer 3

对于您的图中每个P1，P2点，找到所有类似于以下形式的R路：

R =（P1，Pf1，...，Pfn，P2）

对于从P1到P2的每条R1，R2路，如果Intersection（R1，R2）具有多于0个点（当然不包括P1和P2），确定哪条路较短。如果R1的长度小于R2的长度，则忘记R2，否则忘记R1。

在迭代中，您将找到从P1到P2的最短完全分离道路。如果要穿越一条道路，其中您拥有点（P1，...，Pk）如果我们选择Pi，其中1 <= i <= k，则我们知道第一个点将是Pi，最后一个点也将是Pi。

假设顺序无关紧要。每当您穿过一个点时，请标记它为已遍历。如果一个点被标记为已遍历，您将不会再次去给定的点，但如果必要，您将不介意再次穿过该点。因此，计划的路线将是：Pf1，...，Pfk，Pf1。

对于每个Pfj，Pfm：

我们现在在Pfj。如果已经遍历了Pfm，那么我们不想再次去Pfm，所以我们进入下一次迭代。

如果没有遍历Pfm，则从Pfj到Pfm有R1，...，Rq条道路。选择未遍历点数量最多且已遍历道路数量最少的道路。您需要通过巧妙的想法来权衡道路中未遍历点和已遍历点的重要性（希望您的权重将最小化从Pf1到Pf1的总路程）。

请注意，Pf1不应标记为已遍历，因为您希望在算法结束时到达那里。

- Lajos Arpad

Answer 4

我不确定您是想要算法还是想知道如何完成工作。

如果是后者，您可以使用networkx。

一旦您下载并安装了networkx，您可以尝试以下操作：

>>> import networkx as nx
>>> DG=nx.DiGraph()
>>> def CycleFrom(G,node):
    return sorted((c for c in nx.simple_cycles(DG) if node in c), key=len)[0]

>>> for (stnode, edges) in graph.items():
    for (ennode,edge) in edges.items():
        DG.add_edge(stnode,ennode,name=edge)


>>> for node in DG.nodes():
    print "Cycles from {0} is {1}".format(node,CycleFrom(DG,node))


Cycles from A is ['A', 'IDLE', 'A']
Cycles from IDLE is ['A', 'IDLE', 'A']
Cycles from B is ['A', 'B', 'A']
Cycles from C is ['A', 'C', 'A']
>>> 

- Abhijit