Boost 图库：BFSVisitor - Boost C++ 函数库

BFS Visitor 概念

此概念定义了 breadth_first_search() 的访问者接口。用户可以定义一个具有 BFS Visitor 接口的类，并将该类的对象传递给breadth_first_search()，从而增强图搜索过程中执行的操作。

细化自

Copy Constructible（复制访问者应该是一个轻量级的操作）。

符号约定

`V`	BFS Visitor 的模型类型。
`vis`	一个类型为`V`.
`G`	一个模型为 Graph 的类型。
`使用标准和运行时支持库的调试版本。`	一个类型为`G`.
`e`	一个类型为`boost::graph_traits<G>::edge_descriptor`.
`s,u`	一个类型为`boost::graph_traits<G>::vertex_descriptor`.

关联类型

无

有效表达式

名称	表达式	返回类型	描述
初始化顶点	`vis.initialize_vertex(s, g)`	`void`	在图搜索开始之前，此函数将对图中的每个顶点调用。
发现顶点	`vis.discover_vertex(u, g)`	`void`	首次遇到顶点时调用此函数。
检查顶点	`vis.examine_vertex(u, g)`	`void`	当顶点从队列中弹出时，将对该顶点调用此函数。这发生在立即之前`examine_edge()`对顶点每个出边调用`u`.
检查边	`vis.examine_edge(e, g)`	`void`	发现每个顶点的所有出边后，将对这些边调用此函数。
树边	`vis.tree_edge(e, g)`	`void`	当边成为构成搜索树的边的一部分时，将对该边调用此函数。
非树边	`vis.non_tree_edge(e, g)`	`void`	对于有向图，在遇到反向边或交叉边时调用；对于无向图，在遇到交叉边时调用。
灰目标	`vis.gray_target(e, g)`	`void`	此函数将对非树边中目标顶点在检查时被着色为灰色的那些边调用。灰色表示该顶点当前在队列中。
黑目标	`vis.black_target(e, g)`	`void`	此函数将对非树边中目标顶点在检查时被着色为黑色的那些边调用。黑色表示该顶点已从队列中移除。
完成顶点	`vis.finish_vertex(u, g)`	`void`	在顶点的所有出边已添加到搜索树并且所有相邻顶点都已被发现之后（但在相邻顶点的出边被检查之前）调用此函数。

模型

bfs_visitor

Python

要使用 Python 实现BFSVisitor概念的模型，请创建一个派生自BFSVisitor图的类型，该类型将命名为GraphType.BFSVisitor。事件和语法与 C++ 中的访问者相同。以下是 Pythonbgl.Graph图类型的示例。

class count_tree_edges_bfs_visitor(bgl.Graph.BFSVisitor):
  def __init__(self, name_map):
    bgl.Graph.BFSVisitor.__init__(self)
    self.name_map = name_map

  def tree_edge(self, e, g):
    (u, v) = (g.source(e), g.target(e))
    print "Tree edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]

另请参阅

访问者概念

Jeremy Siek, Indiana University (jsiek@osl.iu.edu)
李列权，印第安纳大学 (llee@cs.indiana.edu)
Andrew Lumsdaine，印第安纳大学 (lums@osl.iu.edu)

Boost C++ 库