我使用无向图G，我的目标是找到一对一关系中长于N节点的所有可能的链。
例如:
在下图中，一对一关系中长度超过 2 个节点的“链”是:
- d -> e -> f -> g
- c -> k -> l -> m
那么解决这个问题的最佳方法或算法是什么？
最佳答案
如果你想找到所有路径，使得其中每个顶点的度数<=2，那么简单的方法可能如下。
从图中删除度数 >2 的所有顶点。您将得到一张图，其中每个顶点的度数 <=2。很容易证明这样一个图的每个连接组件要么是一种简单的方式，要么是一个简单的循环，并且很容易区分它们(例如，从一个节点运行 DFS 并查看是否返回到它) .
因此，作为路径的每个组件都是您要查找的路径。作为循环的每个组件也是您寻找的路径，或者可以通过删除边或顶点轻松转换为这样的路径，具体取决于您是否允许循环作为所需的路径。
关于algorithm - 查找图中一对一节点的所有链，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31424668/