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

Question

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

例如：

在下图中，一对一关系中长度大于2的节点"chains"是：

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

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

Answer 1

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

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

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