在无向图（boost）中查找循环并返回它的顶点和边 [英] Find a cycle in an undirected graph (boost) and return its vertices and edges

问题描述

我需要一个函数，它可以在无向图（boost）中找到一个循环并返回它的顶点和边。它只需要返回图中一个周期的顶点/边。
我的问题是 - 使用boost来做这件事的最好方法是什么？如果您想查找 a 循环，那么使用深度第一次搜索应该没问题。 DFS访问者具有back_edge功能。当它被调用时，你在循环中有优势。然后你可以走前辈地图来重建周期。请注意：

• 这里有 strong_components 函数，


• 寻找所有的周期，而不是周期，是一个更难的问题，我相信Boost.Graph目前还没有实现

I need a functions thats find a cycle in an undirected graph (boost) and returns its vertices and edges. It needs only return the vertices/edges of one cycle in the graph. My question is - what is the best way to do this using with boost? I am not experienced using it.

解决方案

If you want to find a cycle, then using depth first search should do just fine. The DFS visitor has a back_edge function. When it's called, you have an edge in the cycle. You can then walk the predecessor map to reconstruct the cycle. Note that:

• There's the strong_components function, to find, well, strong components
• Finding all cycles, as opposed to a cycle, is much harder problem, and I believe Boost.Graph does not have a implementation for that at present

这篇关于在无向图（boost）中查找循环并返回它的顶点和边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！