9.11. Traversal¶
9.11.1. 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. |
9.11.2. 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) |
Returns an iterator of predecessors in breadth-first-search from source. |
bfs_successors(G, source) |
Returns an iterator of successors in breadth-first-search from source. |
9.11.3. Beam search¶
bfs_beam_edges |
9.11.4. 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. |