rustworkx.bfs_search#

bfs_search(graph, source, visitor)[source]#

对有向/无向图进行广度优先遍历，包含多个源顶点。

带有一个源顶点的广度优先搜索算法的伪代码如下所示，其中标注了事件点，在这些事件点上会调用给定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.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.PyGraph()
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.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 – 将被使用的图。这可以是一个 PyGraph 或是一个 PyDiGraph
source – 可选的节点索引列表，用作广度优先搜索的起始节点。如果为 None 或未指定，则将任意选择一个起始节点并重复搜索，直到遍历图中的所有组件。这可以是 Sequence[int] 或 None。
visitor – 一种在算法内部事件点被调用的访问者对象。这应该是 BFSVisitor 的子类。

rustworkx.barabasi_albert_graph

rustworkx.random_bipartite_graph

rustworkx.random_gnm_graph

rustworkx.bfs_search#