breadth_first_search

// named parameter version
template <class Graph, class P, class T, class R>
void breadth_first_search(Graph& G,
  typename graph_traits<Graph>::vertex_descriptor s,
  const bgl_named_params<P, T, R>& params);

// non-named parameter version
template <class Graph, class Buffer, class BFSVisitor,
	  class ColorMap>
void breadth_first_search(const Graph& g,
   typename graph_traits<Graph>::vertex_descriptor s,
   Buffer& Q, BFSVisitor vis, ColorMap color);

breadth_first_search() 函数执行有向图或无向图的广度优先遍历 [49]。广度优先遍历先访问离源顶点较近的顶点，然后再访问距离较远的顶点。在此上下文中，“距离”定义为从源顶点到顶点的最短路径中的边数。该breadth_first_search()函数可用于计算从源顶点到所有可达顶点的最短路径以及由此产生的最短路径距离。有关与 BFS 相关的更多定义，请参见 广度优先搜索 部分。

BFS 使用两个数据结构来实现遍历：每个顶点的颜色标记和一个队列。白色顶点是未发现的，而灰色顶点是已发现但有未发现的相邻顶点的顶点。黑色顶点是已发现的，并且仅与其他黑色或灰色顶点相邻。该算法通过从队列中移除顶点 u 并检查每个出边 (u,v) 来进行。如果相邻顶点 v 尚未被发现，则将其着色为灰色并放入队列中。在检查完所有出边后，顶点 u 被着色为黑色，并重复该过程。BFS 算法的伪代码如下所示。

BFS(G, s)
  for each vertex u in V[G]
    color[u] := WHITE
    d[u] := infinity
    p[u] := u
  end for
  color[s] := GRAY
  d[s] := 0
  ENQUEUE(Q, s)
  while (Q != Ø)
    u := DEQUEUE(Q)
    for each vertex v in Adj[u]
      if (color[v] = WHITE)
        color[v] := GRAY
        d[v] := d[u] + 1
        p[v] := u
        ENQUEUE(Q, v)
      else
        if (color[v] = GRAY)
          ...
        else
          ...
    end for
    color[u] := BLACK
  end while
  return (d, p)

initialize vertex u






discover vertex s

examine vertex u
examine edge (u,v)
(u,v) is a tree edge



discover vertex v
(u,v) is a non-tree edge

(u,v) has a gray target

(u,v) has a black target

finish vertex u

定义位置

boost/graph/breadth_first_search.hpp

参数

有向图或无向图。图类型必须是 Vertex List Graph 和 Incidence Graph 的模型。
Python：参数名为graph.

搜索开始的源顶点。
Python：参数名为root_vertex.

命名参数

在算法内部、由 BFS Visitor 概念指定的事件点调用的访问器对象。访问器对象按值传递 [1]。
默认值 bfs_visitor<null_visitor>
Python：该参数应该是从图的 BFSVisitor 类型派生的对象。

算法使用此项来跟踪其在图中的进度。用户在调用之前无需初始化颜色映射breadth_first_search()，因为算法在算法开始时将每个顶点的颜色初始化为白色。如果需要在图上执行多次广度优先搜索（例如，如果存在一些断开连接的组件），则使用 breadth_first_visit() 函数并执行您自己的颜色初始化。

类型ColorMap必须是 Read/Write Property Map 的模型，并且其键类型必须是图的顶点描述符类型，颜色映射的值类型必须是 ColorValue 的模型。
默认值： 从 iterator_property_map 创建，该映射来自一个std::vector的default_color_type大小为num_vertices(g)并使用i_map作为索引映射。
Python：颜色映射必须是vertex_color_map为了该图。

此参数将每个顶点映射到范围为[0, num_vertices(g))的整数。仅当使用默认颜色属性映射时，此参数才是必要的。类型VertexIndexMap必须是 Readable Property Map 的模型。映射的值类型必须是整数类型。图的顶点描述符类型需要可用作映射的键类型。
默认值 get(vertex_index, g)。注意：如果使用此默认值，请确保您的图具有内部vertex_index属性。例如，adjacency_list与VertexList=listS没有内部vertex_indexproperty。
Python：不支持的参数。

用于确定顶点将被发现的顺序的队列。如果使用 FIFO 队列，则遍历将按照通常的 BFS 顺序进行。可以使用其他类型的队列，但遍历顺序将有所不同。例如，可以使用优先级队列实现 Dijkstra 算法。类型Buffer必须是 Buffer 的模型。
该value_type缓冲区的vertex_descriptor类型。
默认值 boost::queue
Python：缓冲区必须从图的 Buffer 类型派生。

复杂度

时间复杂度为 O(E + V)。

访问器事件点

• vis.initialize_vertex(v, g) 在搜索开始之前对每个顶点调用。
• vis.examine_vertex(u, g) 在每个顶点从队列中移除时调用。
• vis.examine_edge(e, g) 在每个顶点从队列中移除后立即对其每个出边调用。
• vis.tree_edge(e, g) 如果边是树边，则调用（除了examine_edge()）。边 `e` 的目标顶点此时被发现。eis discovered at this time.
• vis.discover_vertex(u, g) 在算法首次遇到顶点 u 时调用。所有更接近源顶点的顶点都已被发现，而距离源顶点更远的顶点尚未被发现。
• vis.non_tree_edge(e, g) 如果边不是树边，则调用（除了examine_edge()) if the edge is not a tree edge.
• vis.gray_target(e, g) 如果在检查时目标顶点被着色为灰色，则调用（除了non_tree_edge()）。颜色灰色表示顶点当前在队列中。
• vis.black_target(e, g) 如果在检查时目标顶点被着色为黑色，则调用（除了non_tree_edge()) if the target vertex is colored black at the time of examination. The color black indicates that the vertex is no longer in the queue.
• vis.finish_vertex(u, g) 在检查完 u 的所有出边并且所有相邻顶点都已被发现后调用。

示例

example/bfs-example.cpp 中的示例演示了在 图 6 中的图上使用 BGL 广度优先搜索算法。文件 example/bfs-example2.cpp 包含相同的示例，不同之处在于使用的adacency_list类具有VertexList和EdgeList设置为listS.

另请参阅

注释

[1] 由于访问器参数是按值传递的，如果您的访问器包含状态，则算法期间对状态的任何更改都将应用于访问器对象的副本，而不是传入的访问器对象。因此，您可能希望访问器通过指针或引用来保存此状态。