rust_algorithms/graph/

traversal.rs

//! Grafni aylanib chiqish: BFS, DFS va ular ustiga qurilgan algoritmlar.

use super::Graph;
use std::collections::VecDeque;

/// **BFS** (Breadth-First Search) — kenglikka qidiruv: to'lqin kabi tarqaladi.
///
/// **G'oya:** navbat (queue) ishlatamiz. Avval boshlang'ich tugunning barcha
/// qo'shnilarini ko'ramiz, keyin ularning qo'shnilarini — ya'ni **qavat-qavat**.
///
/// Shu sababli og'irliksiz grafda BFS **eng qisqa yo'lni** topadi.
///
/// - **Time:** O(V + E), **Space:** O(V).
///
/// Qaytadi: tugunlarni ko'rilgan tartibda.
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, bfs};
///
/// //  0 — 1 — 3
/// //  |
/// //  2
/// 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);
///
/// assert_eq!(bfs(&g, 0), vec![0, 1, 2, 3]);
/// ```
pub fn bfs(g: &Graph, start: usize) -> Vec<usize> {
    let mut korilgan = vec![false; g.node_count()];
    let mut tartib = Vec::new();
    let mut navbat = VecDeque::new();

    korilgan[start] = true;
    navbat.push_back(start);

    while let Some(u) = navbat.pop_front() {
        tartib.push(u);
        for e in g.neighbors(u) {
            if !korilgan[e.to] {
                korilgan[e.to] = true; // navbatga qo'yishda belgilaymiz — takror bo'lmaydi
                navbat.push_back(e.to);
            }
        }
    }
    tartib
}

/// **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);
/// ```
pub fn dfs(g: &Graph, start: usize) -> Vec<usize> {
    let mut korilgan = vec![false; g.node_count()];
    let mut tartib = Vec::new();
    let mut stack = vec![start];

    while let Some(u) = stack.pop() {
        if korilgan[u] {
            continue;
        }
        korilgan[u] = true;
        tartib.push(u);
        // teskari tartibda qo'shamiz — natija rekursiv DFS bilan mos tushadi
        for e in g.neighbors(u).iter().rev() {
            if !korilgan[e.to] {
                stack.push(e.to);
            }
        }
    }
    tartib
}

/// DFS ning rekursiv ko'rinishi — g'oyani ko'rsatish uchun.
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, dfs, dfs_recursive};
///
/// let mut g = Graph::new_undirected(5);
/// for (a, b) in [(0, 1), (1, 2), (0, 3), (3, 4)] {
///     g.add_unweighted_edge(a, b);
/// }
/// assert_eq!(dfs_recursive(&g, 0), dfs(&g, 0));
/// ```
pub fn dfs_recursive(g: &Graph, start: usize) -> Vec<usize> {
    fn go(g: &Graph, u: usize, korilgan: &mut [bool], tartib: &mut Vec<usize>) {
        korilgan[u] = true;
        tartib.push(u);
        for e in g.neighbors(u) {
            if !korilgan[e.to] {
                go(g, e.to, korilgan, tartib);
            }
        }
    }
    let mut korilgan = vec![false; g.node_count()];
    let mut tartib = Vec::new();
    go(g, start, &mut korilgan, &mut tartib);
    tartib
}

/// Bog'liq komponentalar: bir-biriga yetib bo'ladigan tugunlar guruhlari.
///
/// Yo'naltirilmagan graflar uchun. Har bir guruh alohida vektor.
///
/// - **Time:** O(V + E).
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, connected_components};
///
/// let mut g = Graph::new_undirected(5);
/// g.add_unweighted_edge(0, 1);
/// g.add_unweighted_edge(3, 4);
/// // 2 — yolg'iz tugun
///
/// let k = connected_components(&g);
/// assert_eq!(k.len(), 3);
/// assert_eq!(k[0], vec![0, 1]);
/// assert_eq!(k[1], vec![2]);
/// assert_eq!(k[2], vec![3, 4]);
/// ```
pub fn connected_components(g: &Graph) -> Vec<Vec<usize>> {
    let n = g.node_count();
    let mut korilgan = vec![false; n];
    let mut natija = Vec::new();

    for start in 0..n {
        if korilgan[start] {
            continue;
        }
        let mut komponenta = Vec::new();
        let mut stack = vec![start];
        korilgan[start] = true;
        while let Some(u) = stack.pop() {
            komponenta.push(u);
            for e in g.neighbors(u) {
                if !korilgan[e.to] {
                    korilgan[e.to] = true;
                    stack.push(e.to);
                }
            }
        }
        komponenta.sort_unstable();
        natija.push(komponenta);
    }
    natija
}

/// Grafda sikl bormi?
///
/// - **Yo'naltirilmagan grafda:** DFS paytida "ota bo'lmagan ko'rilgan qo'shni" topilsa — sikl.
/// - **Yo'naltirilgan grafda:** hozirgi rekursiya yo'lida turgan tugunga qaytsak — sikl
///   (bu "orqaga qaytuvchi qirra" / back edge deyiladi).
///
/// - **Time:** O(V + E).
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, has_cycle};
///
/// let mut daraxt = Graph::new_undirected(3);
/// daraxt.add_unweighted_edge(0, 1);
/// daraxt.add_unweighted_edge(1, 2);
/// assert!(!has_cycle(&daraxt));
///
/// daraxt.add_unweighted_edge(2, 0); // uchburchak hosil bo'ldi
/// assert!(has_cycle(&daraxt));
/// ```
pub fn has_cycle(g: &Graph) -> bool {
    let n = g.node_count();
    if g.is_directed() {
        // 0 = ko'rilmagan, 1 = hozir yo'lda, 2 = tugagan
        let mut holat = vec![0u8; n];
        fn go(g: &Graph, u: usize, holat: &mut [u8]) -> bool {
            holat[u] = 1;
            for e in g.neighbors(u) {
                if holat[e.to] == 1 {
                    return true; // yo'ldagi tugunga qaytdik → sikl
                }
                if holat[e.to] == 0 && go(g, e.to, holat) {
                    return true;
                }
            }
            holat[u] = 2;
            false
        }
        (0..n).any(|u| holat[u] == 0 && go(g, u, &mut holat))
    } else {
        let mut korilgan = vec![false; n];
        fn go(g: &Graph, u: usize, ota: Option<usize>, korilgan: &mut [bool]) -> bool {
            korilgan[u] = true;
            for e in g.neighbors(u) {
                if e.to == u {
                    return true; // sirtmoq
                }
                if !korilgan[e.to] {
                    if go(g, e.to, Some(u), korilgan) {
                        return true;
                    }
                } else if Some(e.to) != ota {
                    return true;
                }
            }
            false
        }
        (0..n).any(|u| !korilgan[u] && go(g, u, None, &mut korilgan))
    }
}

/// Topologik saralash — yo'naltirilgan asiklik grafda (DAG) bog'liqliklar tartibi.
///
/// **Masala:** "A ni B dan oldin bajarish kerak" turidagi cheklovlar berilgan.
/// Qaysi tartibda bajarsak, hech bir cheklov buzilmaydi?
///
/// **Kahn algoritmi:** kiruvchi qirrasi yo'q (`in_degree == 0`) tugunlarni navbatga
/// solamiz; birini olganimizda uning qirralarini "o'chirib", qo'shnilarining
/// `in_degree` sini kamaytiramiz.
///
/// Sikl bo'lsa (bog'liqliklar aylanma) — `None`.
///
/// - **Time:** O(V + E).
///
/// # Misol: darslarni qaysi tartibda o'qish kerak
/// ```
/// use rust_algorithms::graph::{Graph, topological_sort};
///
/// // 0: Matematika → 1: Algoritmlar → 3: ML
/// //                 2: Rust        → 3
/// let mut g = Graph::new_directed(4);
/// g.add_unweighted_edge(0, 1);
/// g.add_unweighted_edge(1, 3);
/// g.add_unweighted_edge(2, 3);
///
/// let tartib = topological_sort(&g).unwrap();
/// let orin = |x: usize| tartib.iter().position(|&y| y == x).unwrap();
/// assert!(orin(0) < orin(1) && orin(1) < orin(3) && orin(2) < orin(3));
/// ```
pub fn topological_sort(g: &Graph) -> Option<Vec<usize>> {
    let n = g.node_count();
    let mut kiruvchi = vec![0usize; n];
    for u in 0..n {
        for e in g.neighbors(u) {
            kiruvchi[e.to] += 1;
        }
    }

    let mut navbat: VecDeque<usize> = (0..n).filter(|&u| kiruvchi[u] == 0).collect();
    let mut tartib = Vec::with_capacity(n);

    while let Some(u) = navbat.pop_front() {
        tartib.push(u);
        for e in g.neighbors(u) {
            kiruvchi[e.to] -= 1;
            if kiruvchi[e.to] == 0 {
                navbat.push_back(e.to);
            }
        }
    }

    if tartib.len() == n {
        Some(tartib)
    } else {
        None // sikl bor
    }
}

/// Graf ikki bo'lakli (bipartite) mi? — tugunlarni 2 rangga bo'yash mumkinmi,
/// shundayki qo'shnilar har doim turli rangda bo'lsin.
///
/// **Usul:** BFS bilan yurib, har bir qavatni navbatma-navbat bo'yaymiz.
/// Qo'shni bir xil rangga tushsa — bo'lmaydi.
///
/// **Qayerda kerak:** "ikki guruhga bo'lish", "jadval to'qnashuvlari",
/// "toq uzunlikdagi sikl bormi?" masalalari.
///
/// # Misol
/// ```
/// use rust_algorithms::graph::{Graph, is_bipartite};
///
/// let mut kvadrat = Graph::new_undirected(4); // 4 uzunlikdagi sikl — juft
/// for (a, b) in [(0, 1), (1, 2), (2, 3), (3, 0)] {
///     kvadrat.add_unweighted_edge(a, b);
/// }
/// assert!(is_bipartite(&kvadrat).is_some());
///
/// let mut uchburchak = Graph::new_undirected(3); // toq sikl
/// for (a, b) in [(0, 1), (1, 2), (2, 0)] {
///     uchburchak.add_unweighted_edge(a, b);
/// }
/// assert!(is_bipartite(&uchburchak).is_none());
/// ```
pub fn is_bipartite(g: &Graph) -> Option<Vec<u8>> {
    let n = g.node_count();
    let mut rang = vec![u8::MAX; n]; // MAX = bo'yalmagan

    for start in 0..n {
        if rang[start] != u8::MAX {
            continue;
        }
        rang[start] = 0;
        let mut navbat = VecDeque::from([start]);
        while let Some(u) = navbat.pop_front() {
            for e in g.neighbors(u) {
                if rang[e.to] == u8::MAX {
                    rang[e.to] = 1 - rang[u];
                    navbat.push_back(e.to);
                } else if rang[e.to] == rang[u] {
                    return None;
                }
            }
        }
    }
    Some(rang)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn namuna() -> Graph {
        //  0 — 1 — 3
        //  |   |
        //  2 — 4
        let mut g = Graph::new_undirected(5);
        for (a, b) in [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4)] {
            g.add_unweighted_edge(a, b);
        }
        g
    }

    #[test]
    fn bfs_qavat_boyicha() {
        let g = namuna();
        assert_eq!(bfs(&g, 0), vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn dfs_chuqurlikka() {
        let g = namuna();
        let t = dfs(&g, 0);
        assert_eq!(t.len(), 5);
        assert_eq!(t, dfs_recursive(&g, 0));
    }

    #[test]
    fn komponentalar() {
        let mut g = Graph::new_undirected(7);
        g.add_unweighted_edge(0, 1);
        g.add_unweighted_edge(1, 2);
        g.add_unweighted_edge(4, 5);
        let k = connected_components(&g);
        assert_eq!(k, vec![vec![0, 1, 2], vec![3], vec![4, 5], vec![6]]);
    }

    #[test]
    fn sikl_yonaltirilmagan() {
        let mut daraxt = Graph::new_undirected(4);
        daraxt.add_unweighted_edge(0, 1);
        daraxt.add_unweighted_edge(1, 2);
        daraxt.add_unweighted_edge(1, 3);
        assert!(!has_cycle(&daraxt));

        assert!(has_cycle(&namuna()));
    }

    #[test]
    fn sikl_yonaltirilgan() {
        let mut dag = Graph::new_directed(3);
        dag.add_unweighted_edge(0, 1);
        dag.add_unweighted_edge(1, 2);
        dag.add_unweighted_edge(0, 2);
        assert!(!has_cycle(&dag));

        dag.add_unweighted_edge(2, 0);
        assert!(has_cycle(&dag));
    }

    #[test]
    fn topologik_saralash() {
        let mut g = Graph::new_directed(6);
        for (a, b) in [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)] {
            g.add_unweighted_edge(a, b);
        }
        let t = topological_sort(&g).unwrap();
        assert_eq!(t.len(), 6);
        // har bir qirra uchun: from tartibda to dan oldin turishi kerak
        for (from, to, _) in g.all_edges() {
            let i = t.iter().position(|&x| x == from).unwrap();
            let j = t.iter().position(|&x| x == to).unwrap();
            assert!(i < j, "{from} → {to} tartibi buzilgan");
        }
    }

    #[test]
    fn siklli_grafda_topologik_saralash_yoq() {
        let mut g = Graph::new_directed(2);
        g.add_unweighted_edge(0, 1);
        g.add_unweighted_edge(1, 0);
        assert!(topological_sort(&g).is_none());
    }

    #[test]
    fn ikki_bolaklilik() {
        let mut g = Graph::new_undirected(6);
        // 0,2,4 — bir guruh; 1,3,5 — ikkinchi
        for (a, b) in [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)] {
            g.add_unweighted_edge(a, b);
        }
        let rang = is_bipartite(&g).unwrap();
        for (a, b, _) in g.all_edges() {
            assert_ne!(rang[a], rang[b]);
        }
    }
}