Boost库的广度优先搜索算法能否应用于矩阵？

Question

我的任务是找到矩阵中从一个点到另一个点的最短路径。只能朝上、下、左、右四个方向移动。

0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 0 1 0 1 F 0
0 1 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 S 0 1 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0

S - 起点

F - 目的地 (终点)

0 - 自由的格子 (我们可以穿过它们)

1 - "墙" (我们不能穿过它们)

很明显，广度优先搜索是最优解决这个问题的方式。 我知道Boost库提供了这个算法，但我以前没有使用过Boost。

在我的情况下如何使用Boost进行广度优先搜索呢？ 我了解到，Boost的广度优先搜索算法仅适用于图形结构。 我想，将矩阵转换为具有m*n个顶点和m*(n-1)+(m-1)*n条边的图形结构可能不是一个好主意。

我能否将广度优先搜索算法应用于矩阵（而不将其转换为图形结构），还是最好实现自己的广度优先搜索函数呢？

- Lucky Man

Answer 1

（提前道歉这个答案有点长。我有段时间没有使用BGL了，所以我觉得这是一个很好的复习机会。完整代码在这里。）

Boost Graph Library (BGL) 和泛型编程的美妙之处在于，为了利用某个特定算法，您不需要使用任何特定的数据结构。您提供的矩阵以及关于遍历它的规则已经定义了一个图。现在只需要将这些规则编码到一个 traits 类中即可，该 traits 类可以用于利用 BGL 算法。

具体来说，我们要做的是为您的图定义 boost::graph_traits<T> 的一种专门化。假设您的矩阵是按行主格式排列的单个 int 数组。不幸的是，专门为 int[N] 的 graph_traits 并不足够，因为它没有提供有关矩阵尺寸的任何信息。因此，让我们如下定义您的图:

namespace matrix
{
  typedef int cell;

  static const int FREE = 0;
  static const int WALL = 1;

  template< size_t ROWS, size_t COLS >
  struct graph
  {
    cell cells[ROWS*COLS];
  };
}

我在这里使用了组合来处理单元格数据，但如果需要外部管理，则可以轻松使用指针。现在我们有了一个编码矩阵维度的类型，可以用于特化graph_traits。但首先让我们定义一些我们需要的函数和类型。

顶点类型和辅助函数：

namespace matrix
{
  typedef size_t vertex_descriptor;

  template< size_t ROWS, size_t COLS >
  size_t get_row(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & )
  {
    return vertex / COLS;
  }

  template< size_t ROWS, size_t COLS >
  size_t get_col(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & )
  {
    return vertex % COLS;
  }

  template< size_t ROWS, size_t COLS >
  vertex_descriptor make_vertex(
    size_t row,
    size_t col,
    graph< ROWS, COLS > const & )
  {
    return row * COLS + col;
  }
}

遍历顶点的类型和函数:

namespace matrix
{
  typedef const cell * vertex_iterator;

  template< size_t ROWS, size_t COLS >
  std::pair< vertex_iterator, vertex_iterator >
  vertices( graph< ROWS, COLS > const & g )
  {
    return std::make_pair( g.cells, g.cells + ROWS*COLS );
  }

  typedef size_t vertices_size_type;

  template< size_t ROWS, size_t COLS >
  vertices_size_type
  num_vertices( graph< ROWS, COLS > const & g )
  {
    return ROWS*COLS;
  }
}

边缘类型：

namespace matrix
{
  typedef std::pair< vertex_descriptor, vertex_descriptor > edge_descriptor;

  bool operator==(
    edge_descriptor const & lhs,
    edge_descriptor const & rhs )
  {
    return
      lhs.first == rhs.first && lhs.second == rhs.second ||
      lhs.first == rhs.second && lhs.second == rhs.first;
  }

  bool operator!=(
    edge_descriptor const & lhs,
    edge_descriptor const & rhs )
  {
    return !(lhs == rhs);
  }
}

最后，我们还有迭代器和函数来帮助我们遍历顶点和边之间的关系：

namespace matrix
{
  template< size_t ROWS, size_t COLS >
  vertex_descriptor
  source(
    edge_descriptor const & edge,
    graph< ROWS, COLS > const & )
  {
    return edge.first;
  }

  template< size_t ROWS, size_t COLS >
  vertex_descriptor
  target(
    edge_descriptor const & edge,
    graph< ROWS, COLS > const & )
  {
    return edge.second;
  }

  typedef boost::shared_container_iterator< std::vector< edge_descriptor > > out_edge_iterator;

  template< size_t ROWS, size_t COLS >
  std::pair< out_edge_iterator, out_edge_iterator >
  out_edges(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & g )
  {
    boost::shared_ptr< std::vector< edge_descriptor > > edges( new std::vector< edge_descriptor >() );

    if( g.cells[vertex] == FREE )
    {
      size_t
        row = get_row( vertex, g ),
        col = get_col( vertex, g );

      if( row != 0 )
      {
        vertex_descriptor up = make_vertex( row - 1, col, g );

        if( g.cells[up] == FREE )
          edges->push_back( edge_descriptor( vertex, up ) );
      }

      if( row != ROWS-1 )
      {
        vertex_descriptor down = make_vertex( row + 1, col, g );

        if( g.cells[down] == FREE )
          edges->push_back( edge_descriptor( vertex, down ) );
      }

      if( col != 0 )
      {
        vertex_descriptor left = make_vertex( row, col - 1, g );

        if( g.cells[left] == FREE )
          edges->push_back( edge_descriptor( vertex, left ) );
      }

      if( col != COLS-1 )
      {
        vertex_descriptor right = make_vertex( row, col + 1, g );

        if( g.cells[right] == FREE )
          edges->push_back( edge_descriptor( vertex, right ) );
      }
    }

    return boost::make_shared_container_range( edges );
  }

  typedef size_t degree_size_type;

  template< size_t ROWS, size_t COLS >
  degree_size_type
  out_degree(
    vertex_descriptor vertex,
    graph< ROWS, COLS > const & g )
  {
    std::pair< out_edge_iterator, out_edge_iterator > edges = out_edges( vertex, g );
    return std::distance( edges.first, edges.second );
  }
}

现在我们准备定义对 boost::graph_traits 的特化：

namespace boost
{
  template< size_t ROWS, size_t COLS >
  struct graph_traits< matrix::graph< ROWS, COLS > >
  {
    typedef matrix::vertex_descriptor vertex_descriptor;
    typedef matrix::edge_descriptor edge_descriptor;

    typedef matrix::out_edge_iterator out_edge_iterator;
    typedef matrix::vertex_iterator vertex_iterator;

    typedef boost::undirected_tag directed_category;
    typedef boost::disallow_parallel_edge_tag edge_parallel_category;
    struct traversal_category :
      virtual boost::vertex_list_graph_tag,
      virtual boost::incidence_graph_tag {};

    typedef matrix::vertices_size_type vertices_size_type;
    typedef matrix::degree_size_type degree_size_type;

    static vertex_descriptor null_vertex() { return ROWS*COLS; }
  };
}

以下是如何执行广度优先搜索并找到最短路径的方法：

int main()
{
  const size_t rows = 8, cols = 8;

  using namespace matrix;

  typedef graph< rows, cols > my_graph;

  my_graph g =
  {
    FREE, FREE, FREE, FREE, WALL, FREE, FREE, FREE,
    WALL, FREE, FREE, FREE, FREE, FREE, FREE, FREE,
    FREE, FREE, FREE, WALL, FREE, WALL, FREE, FREE,
    FREE, WALL, FREE, WALL, FREE, FREE, FREE, FREE,
    FREE, FREE, FREE, WALL, FREE, FREE, FREE, FREE,
    FREE, FREE, FREE, WALL, FREE, FREE, WALL, FREE,
    FREE, FREE, FREE, FREE, FREE, FREE, WALL, FREE,
    FREE, FREE, FREE, FREE, FREE, FREE, WALL, FREE,
  };

  const vertex_descriptor
    start_vertex = make_vertex( 5, 1, g ),
    finish_vertex = make_vertex( 2, 6, g );

  vertex_descriptor predecessors[rows*cols] = { 0 };

  using namespace boost;

  breadth_first_search(
    g,
    start_vertex,
    visitor( make_bfs_visitor( record_predecessors( predecessors, on_tree_edge() ) ) ).
    vertex_index_map( identity_property_map() ) );

  typedef std::list< vertex_descriptor > path;

  path p;

  for( vertex_descriptor vertex = finish_vertex; vertex != start_vertex; vertex = predecessors[vertex] )
    p.push_front( vertex );

  p.push_front( start_vertex );

  for( path::const_iterator cell = p.begin(); cell != p.end(); ++cell )
    std::cout << "[" << get_row( *cell, g ) << ", " << get_col( *cell, g ) << "]\n" ;

  return 0;
}

输出起点到终点沿最短路径的单元格：

[5, 1]
[4, 1]
[4, 2]
[3, 2]
[2, 2]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[2, 6]

- Andrew Durward

---

这是在 ideone 上运行的代码。我不得不进行一两个更改，以使其能够干净地编译而没有警告。 - Aaron McDaid

@AaronMcDaid 谢谢！我没意识到 ideone 上有 boost。 - Andrew Durward

@AndrewDurward，是的，它适用于C++，但如果您选择C++0x，则不可用。我可能会给他们发电子邮件并要求添加支持！ - Aaron McDaid

Answer 2

你绝对可以使用Boost Graph库来实现这个！该库中算法的实现思路是抽象出任何图形数据结构，而是以迭代器为基础进行操作。例如，要从一个节点移动到另一个节点，算法使用邻接迭代器。你可以查看特定算法，例如BFS，并找出该算法需要哪些概念：在本例中，使用该算法的图必须是“顶点列表图”和“入射图”。请注意，这些不是具体类，而是概念：它们指定如何访问数据结构。该算法还需要一些其他参数，如起始节点和一个属性映射来标记（着色）已经访问的节点。

使用该算法与您的矩阵一起，您需要向算法提供矩阵的“图形视图”：一个节点邻接于其直接相邻的节点，除非相应的邻居被设置为1（显然，您不会走出矩阵的边缘）。创建这样的图并不完全简单，但我认为理解Boost Graph库的工作原理非常有用：即使您不想使用这个特定的库，它也是如何在抽象中实现算法的好例子，使得算法即使在完全意料之外的情况下也适用（好吧，我有偏见：早在Jeremy创建Boost Graph库之前，我就已经写了我的毕业论文，大致上是关于同样的事情，我们提出了基本相同的抽象概念）。

所有这些说法，我认为使用广度优先搜索可能不值得学习Boost图形库的努力：它是如此微不足道的算法，你可能想直接实现它。此外，这看起来非常像一个作业任务，在这种情况下，你可能需要自己实现算法。虽然使用Boost图形库可能会令人印象深刻，但您的教练可能不会这样认为。我认为更令人印象深刻的是以独立于数据结构的方式实现BFS，就像Boost图形库所做的那样，然后使用它。在Boost图形库的指导下，这肯定是可行的，即使作为一项练习（尽管可能比所需的更费力）。顺便说一句，是的，我可以发布代码，但不，我不会。我很乐意帮助解决具体的问题。

- Dietmar Kühl

---

感谢您对BGL的贡献！ - Andrew Durward