周期检测含有多个周期

Sample graph shown by adenine molecule. Atoms are vertices, bonds are edges

有没有办法，我可以找出该图的所有周期？我知道DFS可以通过简单地做DFS来检测周期，直到找到后沿，但是我想知道是否有一种计算上有效的方式来返回单个周期，考虑到图中实际上有3个周期（1 -2-3-4-5-6,4-5-7-8-9,1-2-3-4-9-8-7-5-6）。我有点卡住了，因为它看起来像碳原子属于多个图表，除了强制所有可能的来自每个顶点的路径外，我想不出任何其他方式。

来源

2012-06-03 ejang

您不必从每个顶点查找所有路径。

只有顶点指的3个或更多其他可能属于多个周期

你必须检查仅4,5,6（9）

来源

2012-06-03 17:18:53

等待，不顶部8属于4-5 -7-8-9和1-2-3-4-9-8-7-5-6？ – ejang

顶点8属于两者，您将在检查节点4,5,6上的所有路径时发现两个周期（带有重复项） –

周期检测含有多个周期

回答

相关问题