search - 使用 Boost 的图 breadth_first_search() 在未加权的无向图中查找路径

Question

我正在使用带有无向和未加权边的 adjacency_list 图。我需要找到顶点 u 和顶点 v 之间的最短路径。我应该从 u 开始使用 breadth_first_search() 吗？到达v时，如何获取路径，如何停止搜索？

谢谢！

Answer 1

是的，从你开始做breadth_first_search()。

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

要找到最短路径，请从 v 开始：

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

Answer 2

您应该使用最短路径算法之一，Dijkstra Shortest Path是最合适的，因为您只需要找到两个顶点之间的路径。在 boost 发行版中有一个使用示例。从该函数获取输出有多种选择：通过提供距离属性图或构建前驱图或编写自定义访问者。

Answer 3

您需要使用最小生成树：搜索算法。这是一个非常简单直接的贪心算法。