python - 检查图中的边

Question

因此，给定一个从顶点 S 到 E 的循环图，因为它经过每个顶点，然后在 E 上结束。我的目标是删除所有额外的边，以便只有一条从 S 到 E 的路径。帮助我解决这个问题我有一个名为 check(node) 的函数，我没有给出它的代码，但是如果仍然存在从 S 到 E 的路径，那么它返回 True 或 False，这样所有节点只被访问一次，直到我们在 E 结束。

例子：

计划是从顶点 a 到 b 删除一条边，然后在变异图上运行 check(node) 并查看它是否仍然返回 True，因此我们知道删除该边是安全的，如果返回 False，则将其添加回来。对每条边都这样做，所以只剩下需要的边，但是我不知道如何遍历边。

我将图表存储在字典中

标签： pythonedges

Answer 1

通常，解决此类算法问题的方法是首先弄清楚可以使用哪些算法工具。大多数基本问题都可以用现有算法解决。您的第一个目标是查看您是否可以以不需要修改算法的方式修改问题集（即给定图），因为修改算法会导致难以评估问题的 Big-O。如果无法以任何方式修改图形以使运行黑盒算法变得容易，那么您修改算法。最后的手段是想出自己的算法来解决问题。

如果我的算法记忆是正确的，简而言之，这就是旅行商问题。如果我正确理解您的问题，您需要尽可能短的路径来访问每个节点。您甚至不需要修改给定的图表即可使用该算法。从理论上讲，它应该为您找到所需的路径。只有在算法运行后，您才需要将图形减少到所需的状态。因此，我建议找到一些方法来根据您的规范实施 TSP，并删除不属于解决方案的所有边缘。

这是来自 GeeksForGeeks 的一些示例代码，可以帮助您入门