depth_first_search

scirs2_graph::algorithms::traversal

Function depth_first_search 

Source 
pub fn depth_first_search<N, E, Ix>(
    graph: &Graph<N, E, Ix>,
    source: &N,
) -> Result<Vec<N>>
where
    N: Node + Debug,
    E: EdgeWeight,
    Ix: IndexType,
Expand description

Performs depth-first search (DFS) from a given starting node

§Arguments

  • graph - The graph to traverse
  • source - The source node

§Returns

  • Result<Vec<N>> - The nodes visited in DFS order

§Time Complexity

O(V + E) where V is the number of vertices and E is the number of edges. Each vertex and edge is visited at most once.

§Space Complexity

O(V) for the visited set and stack. In the worst case, the stack can contain all vertices (e.g., in a linear graph).