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. |