pygraphs.bfs_reachable#

bfs_reachable(graph, start, *, max_distance=None, _skip_check=False)[source]#

Extract the vertices that are reachable from a starting vertex.

Parameters:

  • graph (Graph) – An instance of the Graph class representing the graph to be traversed.

  • start (Integral) – The starting vertex index for the BFS.

  • max_distance (Optional[Integral], optional (default: None)) – The maximum distance to search for in the BFS. All vertices that are not reachable within this distance will be ignored.

  • _skip_check (bool)

Returns:

A list of vertex indices representing the vertices that are reachable from the starting vertex in the graph.

Return type:

List[int]

See also

pygraphs.bfs()

Core implementation of BFS.

Examples

Create a simple disconnected graph of 7 vertices and compute the vertices that are reachable from a starting vertex (0) in the graph.

../../_images/graph.png

Disconnected graph with 7 vertices for BFS example. Vertices 0, 1, 2, 3 and 4 are the only vertices that are reachable from vertex 0.#

 1from pygraphs import bfs_reachable, Graph
 2
 3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
 4graph = Graph.from_adjacency(graph)
 5start_vertex = 0
 6max_distance = None
 7
 8reachable_vertices = bfs_reachable(
 9    graph, start_vertex, max_distance=max_distance
10)
11print(reachable_vertices)

[0, 1, 2, 3, 4]

This method can be applied for directed graphs as well, where the adjacency list represents the outgoing neighbors of each vertex.

../../_images/graph_directed.png

Directed graph with 7 vertices for BFS example. Vertices 5 is not reachable from vertex 6.#

 1from pygraphs import bfs_reachable, Graph
 2
 3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
 4
 5graph = Graph.from_adjacency(graph)
 6start_vertex = 6
 7max_distance = None
 8
 9reachable_vertices = bfs_reachable(
10    graph, start_vertex, max_distance=max_distance
11)
12print(reachable_vertices)

[6]