- dfs_edges(graph, source=None)#
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
If the input is an undirected graph with a single connected component, the output of this function is a spanning tree.
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.
A list of edges as a tuple of the form
(source, target)in depth-first order
- Return type: