Skip to main content
`Ctrl`+`K`

# bfs_edges

bfs_edges(G, source, reverse=False, depth_limit=None, sort_neighbors=None)

  Iterate over edges in a breadth-first-search starting at source.

  Parameters:
    G NetworkX graph
    source node

      Specify starting node for breadth-first search; this function iterates over only those edges in the component reachable from this node.

    reverse bool, optional

      If True traverse a directed graph in the reverse direction

    depth_limit int, optional(default=len(G))

      Specify the maximum search depth

    sort_neighbors function (default=None)

      A function that takes an iterator over nodes as the input, and returns an iterable of the same nodes with a custom ordering. For example, `sorted` will sort the nodes in increasing order.

  Yields:
    edge: 2-tuple of nodes

      Yields edges resulting from the breadth-first search.

  See also

  `bfs_tree`
  `dfs_edges()`
  `edge_bfs()`

  Notes

  The naming of this function is very similar to `edge_bfs()`. The difference is that `edge_bfs` yields edges even if they extend back to an already explored node while this generator yields the edges of the tree that results from a breadth-first-search (BFS) so no edges are reported if they extend to already explored nodes. That means `edge_bfs` reports all edges while `bfs_edges` only reports those traversed by a node-based BFS. Yet another description is that `bfs_edges` reports the edges traversed during BFS while `edge_bfs` reports all edges in the order they are explored.

  Based on the breadth-first search implementation in PADS [1] by D. Eppstein, July 2004; with modifications to allow depth limits as described in [2].

  References

  [1]

  http://www.ics.uci.edu/~eppstein/PADS/BFS.py.

  [2]

  https://en.wikipedia.org/wiki/Depth-limited_search

  Examples

  To get the edges in a breadth-first search:

      >>> G = nx.path_graph(3)
      >>> list(nx.bfs_edges(G, 0))
      [(0, 1), (1, 2)]
      >>> list(nx.bfs_edges(G, source=0, depth_limit=1))
      [(0, 1)]

  To get the nodes in a breadth-first search order:

      >>> G = nx.path_graph(3)
      >>> root = 2
      >>> edges = nx.bfs_edges(G, root)
      >>> nodes = [root] + [v for u, v in edges]
      >>> nodes
      [2, 1, 0]