pygraphs.dfs_reachable#

dfs_reachable(graph, start, *, _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 DFS.

  • _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.dfs()

Core implementation of DFS.

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 DFS example. Vertices 0, 1, 2, 3 and 4 are the only vertices that are reachable from vertex 0.#

 1from pygraphs import dfs_reachable, Graph
 2
 3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
 4graph = Graph.from_adjacency(graph)
 5start_vertex = 0
 6
 7reachable_vertices = dfs_reachable(
 8    graph, start_vertex
 9)
10print(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 DFS example. Vertices 5 is not reachable from vertex 6.#

 1from pygraphs import dfs_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 = dfs_reachable(
10    graph, start_vertex, max_distance=max_distance
11)
12print(reachable_vertices)

[6]