c++ - 如何获得 boost 图中顶点的最大级别(深度)

Question

一般来说，我是 boost 图和图论的新手。碰巧我对图形算法术语的了解有限，这让我遇到了困难。无论如何，这就是我想要做的。

我正在使用 boost::adjacency_list 假设我有一个顶点

struct Node {
    int level;
}

现在我构建了一个完整的图，我想找到每个节点的级别。对我来说，级别在这里意味着从根节点开始的最大深度。例如考虑图(假设 118 是根节点)

118 -> 122
118 -> 120
122 -> 120
122 -> 121
121 -> 125
121 -> 123
123 -> 125
125 -> 124

那么 122 的等级是 1，120 是 2，121 是 2，123 是 3，125 是 4，124 是 5。

boost 中是否有任何算法可以让我这样做。我敢打赌它是 boost::bredth_first_visit。但我不确定如何正确使用它，以便它在访问时将正确的值放入 Node.level 中。

我在类似问题上发现了另一篇关于堆栈溢出的帖子，这是一种解决方案(它不是为我编译的。)

typedef boost::property_map<TaskGraph, boost::vertex_color_t>::type color_map_t;
color_map_t colorMap; //Create a color map
boost::breadth_first_visit(graph, *boost::vertices(graph).first, boost::color_map(colorMap));

我想做的是类似

boost::breadth_first_visit(graph, *boost::vertices(graph).first, /*What goes here so that Node.level gets the level*/);

感谢您的帮助，对术语感到抱歉。不确定 level 是否是图论中的正确术语。

Answer 1

看看Dijkstra's Algorithm .没有简单的方法可以做到这一点，boost::breadth_first_visit 将遍历每个节点，但请记住，您仍然需要计算“级别”，我将其称为成本。

假设您有这张图:

   a->b
   b->c
   a->c

C的“等级”是多少，二级还是三级？在这里，您可能希望改用术语“成本”。此处，成本最低的选项是 2。在这种情况下，如果每个 C 有两个父指针，则需要递归地遍历每个父指针，返回起始节点，从而增加成本。

看起来像这样:

   cost=1
   c->b
       cost=2
       b->a
           cost=3 
   c->a
       cost=2