rustworkx.dfs_edges#

dfs_edges(graph, source=None)[source]#

Get an edge list of the tree edges from a depth-first traversal

The pseudo-code for the DFS algorithm is listed below. The output contains the tree edges found by the procedure.

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

Note

If the input is an undirected graph with a single connected component, the output of this function is a spanning tree.

Parameters:

  • graph – The graph to get the DFS edge list from. Can either be a PyGraph or PyDiGraph

  • source (int) – An optional node index to use as the starting node for the depth-first search. The edge list will only return edges in the components reachable from this index. If this is not specified then a source will be chosen arbitrarly and repeated until all components of the graph are searched.

Returns:

A list of edges as a tuple of the form (source, target) in depth-first order

Return type:

EdgeList