bfs_edges#

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

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

Parameters:
GNetworkX graph
sourcenode

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

reversebool, optional

If True traverse a directed graph in the reverse direction

depth_limitint, optional(default=len(G))

Specify the maximum search depth

sort_neighborsfunction

A function that takes the list of neighbors of given node as input, and returns an iterator over these neighbors but with custom ordering.

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

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]