遍历图中所有边的算法

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'}
}

Answer 1

方法一

您可以将图 G 更改为新图 G'，其中 G 中的每条边都成为 G' 中的一个节点。如果对于某些 A、B 和 C，在 G 中可能出现“A -> t1 -> B -> t2 -> C”，则在 G' 中制作从 t1 到 t2 的边。

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

方法二

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