rustworkx.digraph_bfs_search#

digraph_bfs_search(graph, source=None, visitor=None)#

对具有多个源顶点的有向图进行广度优先遍历。

带有一个源顶点的广度优先搜索算法的伪代码如下所示，其中标注了事件点，在这些事件点上会调用给定BFSVisitor的方法。

# G - graph, s - single source node
BFS(G, s)
  let color be a mapping             # color[u] - vertex u color WHITE/GRAY/BLACK
  for each u in G                    # u - vertex in G
    color[u] := WHITE                # color all vertices as undiscovered
  end for
  let Q be a queue
  ENQUEUE(Q, s)
  color[s] := GRAY                   # event: discover_vertex(s)
  while (Q is not empty)
    u := DEQUEUE(Q)
    for each v, w in OutEdges(G, u)  # v - target vertex, w - edge weight
      if (WHITE = color[v])          # event: tree_edge((u, v, w))
        color[v] := GRAY             # event: discover_vertex(v)
        ENQUEUE(Q, v)
      else                           # event: non_tree_edge((u, v, w))
        if (GRAY = color[v])         # event: gray_target_edge((u, v, w))
          ...                       
        elif (BLACK = color[v])      # event: black_target_edge((u, v, w))
          ...                       
    end for
    color[u] := BLACK                # event: finish_vertex(u)
  end while

对于多个源节点，BFS算法会按照给定的顺序依次在源节点上应用。

如果在BFSVisitor实例的回调方法中引发异常，图形遍历将被立即停止。你可以通过引发StopSearch异常来利用此功能提前退出，在这种情况下，搜索函数将会返回但不会重新引发异常。你也可以通过引发PruneSearch来剪枝部分搜索树。

在以下示例中，我们追踪树的边：

import rustworkx as rx
from rustworkx.visit import BFSVisitor

class TreeEdgesRecorder(BFSVisitor):

    def __init__(self):
        self.edges = []

    def tree_edge(self, edge):
        self.edges.append(edge)

graph = rx.PyDiGraph()
graph.extend_from_edge_list([(1, 3), (0, 1), (2, 1), (0, 2)])
vis = TreeEdgesRecorder()
rx.digraph_bfs_search(graph, [0], vis)
print('Tree edges:', vis.edges)

Tree edges: [(0, 2, None), (0, 1, None), (1, 3, None)]

这是一个使用 PruneSearch 异常机制的另一个示例，用于在边上有某些限制条件时寻找两个顶点之间的最短路径（更高效的寻找最短路径方法，请参阅 Shortest Paths）：

import rustworkx as rx
from rustworkx.visit import BFSVisitor, PruneSearch


graph = rx.PyDiGraph()
home, market, school = graph.add_nodes_from(['home', 'market', 'school'])
graph.add_edges_from_no_data(
    [(school, home), (school, market), (market, home)]
)

class DistanceHomeFinder(BFSVisitor):

    def __init__(self):
        self.distance = {}

    def discover_vertex(self, vertex):
        self.distance.setdefault(vertex, 0)

    def tree_edge(self, edge):
        source, target, _ = edge
        # the road directly from home to school is closed
        if {source, target} == {home, school}:
            raise PruneSearch
        self.distance[target] = self.distance[source] + 1

vis = DistanceHomeFinder()
rx.digraph_bfs_search(graph, [school], vis)
print('Distance from school to home:', vis.distance[home])

Distance from school to home: 2

注意

遍历过程中，图结构不能被修改。试图这样做会引发异常。

注意

如果在finish_vertex事件中触发了PruneSearch，将引发异常。

Parameters:

graph (PyDiGraph) – 要使用的图形。
source – 可选的一个节点索引列表，用作广度优先搜索的起始节点。如果为 None 或未指定，则会任意选择一个源节点，并重复操作直到搜索完图的所有连通分量。这可以是 Sequence[int] 或 None。
visitor – A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of BFSVisitor. This has a default value of None as a backwards compatibility artifact (to preserve argument ordering from an earlier version) but it is a required argument and will raise a TypeError if not specified.

rustworkx.barabasi_albert_graph

rustworkx.random_bipartite_graph

rustworkx.random_gnm_graph

rustworkx.digraph_bfs_search#