Skip to main content

dfs

Function dfs 

Source
pub fn dfs(g: &Graph, start: usize) -> Vec<usize>
Expand description

DFS (Depth-First Search) — chuqurlikka qidiruv: bir yo’ldan oxirigacha borib, keyin orqaga qaytadi (backtrack).

Bu yerda stack bilan iterativ implementatsiya — chuqur graflarda ham stack overflow bo’lmaydi.

  • Time: O(V + E), Space: O(V).

§Misol

use rust_algorithms::graph::{Graph, dfs};

let mut g = Graph::new_undirected(4);
g.add_unweighted_edge(0, 1);
g.add_unweighted_edge(0, 2);
g.add_unweighted_edge(1, 3);

let tartib = dfs(&g, 0);
assert_eq!(tartib.len(), 4);
assert_eq!(tartib[0], 0);