查找图中一对一节点的所有链

Question

我使用无向图，G我的目标是找到比N 一对一关系中的节点最长的所有可能的链。

例如：

在下一张图中，一对一关系中长度超过 2 个节点的“链”是：

- d -> e -> f -> g
- c -> k -> l -> m

那么解决这个问题的最佳方法或算法是什么？

Answer 1

如果你想找到所有路径，使得其中每个顶点的度数<=2，那么简单的方法可能如下。

从图中删除度数 >2 的所有顶点。您将得到一张图，其中每个顶点的度数 <=2。很容易证明这样一个图的每个连接组件要么是一种简单的方式，要么是一个简单的循环，并且很容易区分它们（例如，从一个节点运行 DFS 并查看是否返回到它） 。

因此，作为路径的每个组件都是您要寻找的路径。作为循环的每个组件也是您寻找的路径，或者可以通过删除边或顶点轻松转换为这样的路径，具体取决于您是否允许循环作为所需的路径。