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 (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
Notes
The naming of this function is very similar to
edge_bfs()
. The difference is thatedge_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 meansedge_bfs
reports all edges whilebfs_edges
only reports those traversed by a node-based BFS. Yet another description is thatbfs_edges
reports the edges traversed during BFS whileedge_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]
Additional backends implement this function
- cugraphGPU-accelerated backend.
sort_neighbors
parameter is not yet supported.