Boost Graph 库中两个节点之间的所有路径

Question

我需要找到图中两个节点之间的所有简单（非循环）路径。我了解如何通过修改后的广度优先搜索来实现这一点，所以我正在查看 Boost 中的 BFS，但我看不到如何更改算法的步骤，只能更改访问者。

在我继续从头开始编写新算法之前，有没有一种方法可以通过使用现有算法在 BGL 中实现这一点，有或没有自定义访问者？

Answer 1

我们可能需要更多地了解您的图表。我有一个 "similar" 问题。

这可能不是您要查找的内容，但它是相似的。这是我在有向图上使用的 DFS 访问者，它有一个根来计算从起始节点到所有其他（可达）节点的路径数。

这是可行的，因为我的图是一个有根的 DAG。我必须先反转图形，这样我的起始节点实际上是一个汇节点。然后源节点成为 DAG 的根。如果我想要实际路径，我可能会添加一个堆栈来告知路径历史记录。

//depth first search to calculate path number, calculates the number of paths to a target
// conceptually equivalent to a topological sort.
class PathNumDFSVisitor:public boost::default_dfs_visitor{

public:
    PathNumDFSVisitor(boost::unordered_map<std::string,std::size_t>& inMap):pathNumMap(inMap){}

    template < typename Vertex, typename Graph >
    void finish_vertex(Vertex u, const Graph & g)
    {
        std::string term = g[u].termId;

        if(boost::out_degree(u,g) == 0){
            pathNumMap[term] = 1;
        }else{
            pathNumMap[term] = 0;
            //Iterate over the children of the term to add the child annotations
            typename boost::graph_traits< Graph >::out_edge_iterator ei, e_end;
            for(tie(ei, e_end) = boost::out_edges(u, g); ei != e_end; ++ei){

                Vertex v = boost::target(*ei, g);

                std::string childTermId = g[v].termId;
                pathNumMap[term] += pathNumMap[childTermId];
            }
        }
    }

    boost::unordered_map<std::string,std::size_t>& pathNumMap;
};

但在一般情况下，我建议计算最短路径，然后依次取每条边并找到从源到目标的备用路径。现在该边缘可能是两条或更多条边缘，而这又需要放宽并考虑替代路径。就像Sehe说的那样，它就是一个生成器，而且它可以在一般的无向图中快速爆炸。也许如果我们对您的图形约束了解更多一点，我们可以提供更多帮助。

也许添加最大路径长度条件可以帮助限制您生成的简单路径的数量。

考虑这个通用的全连接图。

我们需要计算A和B之间的所有路径。

所以我们需要所有 1 条边路径 + 所有 2 条边路径加上 ...

所以我们需要A - B，一条边。

然后是所有 2 条边路径。 A - ? - B, 有3个

然后所有3条边路径 A - ? - ? - B, 有3 * 2.

以此类推，有 4 个或更多边。

你可以看到随着 N 的增长，我们达到 N-2 * N-3 * N-4 ... 等等。这是阶乘爆炸，O(N!)。

这些示例说明了不同的拓扑结构如何导致截然不同的算法和复杂性。要从 SO 中获得 straight/helpful 答案，请提供任何有帮助的详细信息。

Boost Graph 库中两个节点之间的所有路径

All paths between two nodes in Boost Graph Library

c++

boost

graph-theory

boost-graph