首页 文章

在无向图(boost)中查找循环并返回其顶点和边

提问于
浏览
3

我需要一个函数,它在无向图(boost)中找到一个循环并返回它的顶点和边 . 它只需返回图中一个周期的顶点/边 . 我的问题是 - 使用boost进行此操作的最佳方法是什么?我没有使用它的经验 .

3 回答

  • 1

    我不知道Boost,但here是S.O.的回答 . 在概念层面:

    这是我的猜测:使用BFS浏览图表 . 在每个节点上记下它的“深度”并添加对“父”的引用(即使有很多循环也应该只有一个) . 一旦您发现从A到B的链接创建了一个循环(因为B已经着色),那么:1)从A回溯到根,沿途保存边/顶点 . 2)从B回溯到根部,沿途保存边缘/顶点 . 3)添加A,B,AB 4)“排序”以恢复正确的顺序 . 考虑使用1)的LIFO(堆栈)和2的FIFO

    我希望这有帮助 .

  • 2

    通常,您可以通过深度优先搜索来执行此操作 . 我'm not intimately familiar with boost'的图形工具,但this page将为您提供算法的概述 .

  • 3

    如果你想找到 a 循环,那么使用深度优先搜索应该做得很好 . DFS访问者具有back_edge功能 . 当它被调用时,你在循环中有一个优势 . 然后,您可以遍历前一个映射以重建循环 . 注意:

    • strong_components 功能,可以找到强大的组件

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

相关问题