breadth_first_search

scirs2_graph::algorithms::traversal

Function breadth_first_search 

Source 
pub fn breadth_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 breadth-first search (BFS) from a given starting node

§Arguments

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

§Returns

  • Result<Vec<N>> - The nodes visited in BFS 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 queue.