rustworkx.digraph_dfs_edges#

digraph_dfs_edges(graph, /, source=None)#

从深度优先遍历中获取树边的边列表

DFS 算法的伪代码如下所示。输出包含该过程找到的树边。

DFS(G, v)
  let S be a stack
  label v as discovered
  PUSH(S, (v, iterator of G.neighbors(v)))
  while (S != Ø)
      let (v, iterator) := LAST(S)
      if hasNext(iterator) then
          w := next(iterator)
          if w is not labeled as discovered then
              label w as discovered                   # (v, w) is a tree edge
              PUSH(S, (w, iterator of G.neighbors(w)))
      else
          POP(S)
  end while
Parameters:

  • graph (PyDiGraph) - 要获取深度优先搜索边列表的图

  • source (int) – 一个可选的节点索引，用作深度优先搜索的起始节点。边列表将仅返回该索引可达组件中的边。如果未指定，则将任意选择源节点，并重复此过程直到搜索完图的所有组件。

Returns:

边的列表，形式为深度优先顺序的元组：(source, target)

Return type:

EdgeList