algorithm - 在图中找到一对一节点的所有链

Question

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

例如：

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

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

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

Answer 1

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

从图中删除所有度数 > 2 的顶点。你留下了一个图，每个顶点的度数<=2。很容易证明这样一个图的每个连通分量要么是简单的路，要么是简单的循环，而且很容易区分它们（例如，从一个节点运行 DFS 并查看是否返回到它） .

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