Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Traversal

Depth First Search

Depth-first search

Basic algorithms for depth-first searching the nodes of a graph.

Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py by D. Eppstein, July 2004.

dfs_edges(G[, source])	Produce edges in a depth-first-search (DFS).
dfs_tree(G, source)	Return oriented tree constructed from a depth-first-search from source.
dfs_predecessors(G[, source])	Return dictionary of predecessors in depth-first-search from source.
dfs_successors(G[, source])	Return dictionary of successors in depth-first-search from source.
dfs_preorder_nodes(G[, source])	Produce nodes in a depth-first-search pre-ordering starting from source.
dfs_postorder_nodes(G[, source])	Produce nodes in a depth-first-search post-ordering starting from source.
dfs_labeled_edges(G[, source])	Produce edges in a depth-first-search (DFS) labeled by type.

Breadth First Search

Breadth-first search

Basic algorithms for breadth-first searching the nodes of a graph.

bfs_edges(G, source[, reverse])	Produce edges in a breadth-first-search starting at source.
bfs_tree(G, source[, reverse])	Return an oriented tree constructed from of a breadth-first-search starting at source.
bfs_predecessors(G, source)	Return dictionary of predecessors in breadth-first-search from source.
bfs_successors(G, source)	Return dictionary of successors in breadth-first-search from source.

Depth First Search on Edges

Depth First Search on Edges

Algorithms for a depth-first traversal of edges in a graph.

edge_dfs(G[, source, orientation])

A directed, depth-first traversal of edges in G, beginning at source.