pygraphs.bfs_is_reachable#

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

Check if a vertex is 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.

  • end (Integral) – The ending 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:

If the ending vertex is reachable from starting vertex within the given distance.

Return type:

bool

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_reachable()

Perform a breadth-first search (BFS) to extract the vertices that are reachable from a starting vertex in the graph.

Examples

Create a simple disconnected graph of 7 vertices and check if a vertex is reachable from an other.

../../_images/graph.png

Disconnected graph with 7 vertices for BFS example. Vertex 4 is reachable from vertex 0.#

1from pygraphs import bfs_is_reachable, Graph
2
3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
4graph = Graph.from_adjacency(graph)
5start_vertex = 0
6end_vertex = 4
7
8is_reach = bfs_is_reachable(graph, start_vertex, end_vertex)
9print(is_reach)

True

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. Vertex 5 is not reachable from vertex 6.#

1from pygraphs import bfs_is_reachable, Graph
2
3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5start_vertex = 6
6end_vertex = 5
7
8is_reach = bfs_is_reachable(graph, start_vertex, end_vertex)
9print(is_reach)

False