我需要一个函数,它在无向图(boost)中找到一个循环并返回它的顶点和边 . 它只需返回图中一个周期的顶点/边 . 我的问题是 - 使用boost进行此操作的最佳方法是什么?我没有使用它的经验 .
我不知道Boost,但here是S.O.的回答 . 在概念层面:
这是我的猜测:使用BFS浏览图表 . 在每个节点上记下它的“深度”并添加对“父”的引用(即使有很多循环也应该只有一个) . 一旦您发现从A到B的链接创建了一个循环(因为B已经着色),那么:1)从A回溯到根,沿途保存边/顶点 . 2)从B回溯到根部,沿途保存边缘/顶点 . 3)添加A,B,AB 4)“排序”以恢复正确的顺序 . 考虑使用1)的LIFO(堆栈)和2的FIFO
我希望这有帮助 .
通常,您可以通过深度优先搜索来执行此操作 . 我'm not intimately familiar with boost'的图形工具,但this page将为您提供算法的概述 .
如果你想找到 a 循环,那么使用深度优先搜索应该做得很好 . DFS访问者具有back_edge功能 . 当它被调用时,你在循环中有一个优势 . 然后,您可以遍历前一个映射以重建循环 . 注意:
有 strong_components 功能,可以找到强大的组件
strong_components
找到所有周期,而不是周期,是一个更难的问题,我相信Boost.Graph目前还没有实现
3 回答
我不知道Boost,但here是S.O.的回答 . 在概念层面:
这是我的猜测:使用BFS浏览图表 . 在每个节点上记下它的“深度”并添加对“父”的引用(即使有很多循环也应该只有一个) . 一旦您发现从A到B的链接创建了一个循环(因为B已经着色),那么:1)从A回溯到根,沿途保存边/顶点 . 2)从B回溯到根部,沿途保存边缘/顶点 . 3)添加A,B,AB 4)“排序”以恢复正确的顺序 . 考虑使用1)的LIFO(堆栈)和2的FIFO
我希望这有帮助 .
通常,您可以通过深度优先搜索来执行此操作 . 我'm not intimately familiar with boost'的图形工具,但this page将为您提供算法的概述 .
如果你想找到 a 循环,那么使用深度优先搜索应该做得很好 . DFS访问者具有back_edge功能 . 当它被调用时,你在循环中有一个优势 . 然后,您可以遍历前一个映射以重建循环 . 注意:
有
strong_components
功能,可以找到强大的组件找到所有周期,而不是周期,是一个更难的问题,我相信Boost.Graph目前还没有实现