rust_algorithms/graph/
mst.rs

1//! Minimal bog'lovchi daraxt (Minimum Spanning Tree): Kruskal va Prim.
2//!
3//! **Masala:** hamma tugunni bir-biriga bog'lash uchun eng arzon qirralar to'plamini
4//! tanlang. Natija — daraxt (V−1 ta qirra, siklsiz).
5//!
6//! **Real hayotda:** shaharlarni optik kabel bilan bog'lash, elektr tarmog'i
7//! rejalashtirish, klasterlash (bir necha eng qimmat qirrani olib tashlab).
8
9use super::Graph;
10use crate::data_structures::{DisjointSet, MinHeap};
11use std::cmp::Reverse;
12use std::collections::BinaryHeap;
13
14/// MST natijasi: `(umumiy og'irlik, tanlangan qirralar)`.
15pub type MstResult = Option<(i64, Vec<(usize, usize, i64)>)>;
16
17/// **Kruskal** — qirralarni arzonidan boshlab tanlash (ochko'z algoritm).
18///
19/// **G'oya:**
20/// 1. Barcha qirralarni og'irligi bo'yicha tartiblaymiz;
21/// 2. Har birini navbatma-navbat olamiz: agar u **sikl hosil qilmasa** — MST ga qo'shamiz.
22/// 3. "Sikl hosil qiladimi?" savoliga [`DisjointSet`] deyarli O(1) da javob beradi.
23///
24/// - **Time:** O(E log E) — asosiy vaqt tartiblashga ketadi. **Space:** O(V).
25/// - Siyrak graflarda Primdan qulayroq.
26///
27/// Qaytadi: `(umumiy_ogirlik, qirralar)`. Graf bog'liq bo'lmasa — `None`
28/// (bu holda natija "o'rmon" bo'ladi, daraxt emas).
29///
30/// # Misol
31/// ```
32/// use rust_algorithms::graph::{Graph, kruskal};
33///
34/// let mut g = Graph::new_undirected(4);
35/// g.add_edge(0, 1, 10);
36/// g.add_edge(0, 2, 6);
37/// g.add_edge(0, 3, 5);
38/// g.add_edge(1, 3, 15);
39/// g.add_edge(2, 3, 4);
40///
41/// let (ogirlik, qirralar) = kruskal(&g).unwrap();
42/// assert_eq!(ogirlik, 19);       // 4 + 5 + 10
43/// assert_eq!(qirralar.len(), 3); // V − 1
44/// ```
45pub fn kruskal(g: &Graph) -> MstResult {
46    let n = g.node_count();
47    if n == 0 {
48        return Some((0, Vec::new()));
49    }
50
51    let mut qirralar = g.all_edges();
52    qirralar.sort_by_key(|&(_, _, w)| w); // arzonidan qimmatiga
53
54    let mut ds = DisjointSet::new(n);
55    let mut mst = Vec::with_capacity(n - 1);
56    let mut jami = 0i64;
57
58    for (u, v, w) in qirralar {
59        // union() false qaytarsa — u va v allaqachon bog'langan, bu qirra sikl yasaydi
60        if ds.union(u, v) {
61            mst.push((u, v, w));
62            jami += w;
63            if mst.len() == n - 1 {
64                break; // daraxt to'ldi
65            }
66        }
67    }
68
69    if mst.len() == n - 1 {
70        Some((jami, mst))
71    } else {
72        None // graf bog'liq emas
73    }
74}
75
76/// **Prim** — daraxtni bitta tugundan boshlab "o'stirish".
77///
78/// **G'oya:** MST ni bitta tugundan boshlaymiz va har qadamda daraxtni tashqi
79/// dunyoga bog'laydigan **eng arzon** qirrani qo'shamiz. Nomzod qirralarni
80/// min-heapda saqlaymiz.
81///
82/// - **Time:** O(E log V), **Space:** O(V + E).
83/// - Zich graflarda (E ≈ V²) Kruskaldan tezroq.
84///
85/// # Misol
86/// ```
87/// use rust_algorithms::graph::{Graph, kruskal, prim};
88///
89/// let mut g = Graph::new_undirected(5);
90/// for (a, b, w) in [(0, 1, 2), (0, 3, 6), (1, 2, 3), (1, 3, 8), (1, 4, 5), (2, 4, 7), (3, 4, 9)] {
91///     g.add_edge(a, b, w);
92/// }
93///
94/// let (prim_w, _) = prim(&g).unwrap();
95/// let (kruskal_w, _) = kruskal(&g).unwrap();
96/// assert_eq!(prim_w, kruskal_w); // ikkalasi ham 16
97/// ```
98pub fn prim(g: &Graph) -> MstResult {
99    let n = g.node_count();
100    if n == 0 {
101        return Some((0, Vec::new()));
102    }
103
104    let mut daraxtda = vec![false; n];
105    let mut mst = Vec::with_capacity(n - 1);
106    let mut jami = 0i64;
107
108    // (og'irlik, qayerdan, qayerga) — Reverse bilan min-heap
109    let mut heap = BinaryHeap::new();
110    daraxtda[0] = true;
111    for e in g.neighbors(0) {
112        heap.push(Reverse((e.weight, 0usize, e.to)));
113    }
114
115    while let Some(Reverse((w, from, to))) = heap.pop() {
116        if daraxtda[to] {
117            continue; // bu tugun allaqachon daraxtda — qirra sikl yasaydi
118        }
119        daraxtda[to] = true;
120        mst.push((from, to, w));
121        jami += w;
122
123        for e in g.neighbors(to) {
124            if !daraxtda[e.to] {
125                heap.push(Reverse((e.weight, to, e.to)));
126            }
127        }
128    }
129
130    if mst.len() == n - 1 {
131        Some((jami, mst))
132    } else {
133        None
134    }
135}
136
137/// Ichki tekshiruv: `MinHeap` ham shu maqsadda ishlatilishi mumkinligini ko'rsatadi.
138#[allow(dead_code)]
139fn min_heap_bilan_misol(ogirliklar: Vec<i64>) -> Vec<i64> {
140    let heap: MinHeap<i64> = ogirliklar.into_iter().collect();
141    heap.into_sorted_vec()
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use crate::util::Rng;
148
149    fn namuna() -> Graph {
150        let mut g = Graph::new_undirected(7);
151        for (a, b, w) in [
152            (0, 1, 7),
153            (0, 3, 5),
154            (1, 2, 8),
155            (1, 3, 9),
156            (1, 4, 7),
157            (2, 4, 5),
158            (3, 4, 15),
159            (3, 5, 6),
160            (4, 5, 8),
161            (4, 6, 9),
162            (5, 6, 11),
163        ] {
164            g.add_edge(a, b, w);
165        }
166        g
167    }
168
169    #[test]
170    fn kruskal_klassik_misol() {
171        let (w, qirralar) = kruskal(&namuna()).unwrap();
172        assert_eq!(w, 39); // ma'lum javob
173        assert_eq!(qirralar.len(), 6);
174    }
175
176    #[test]
177    fn prim_va_kruskal_bir_xil_ogirlik() {
178        let mut rng = Rng::new(606);
179        for _ in 0..30 {
180            let n = 8;
181            let mut g = Graph::new_undirected(n);
182            // bog'liqlikni kafolatlash uchun avval zanjir quramiz
183            for i in 1..n {
184                g.add_edge(i - 1, i, rng.range(1, 50));
185            }
186            for _ in 0..12 {
187                let (a, b) = (rng.below(n), rng.below(n));
188                if a != b {
189                    g.add_edge(a, b, rng.range(1, 50));
190                }
191            }
192            let (kw, ke) = kruskal(&g).unwrap();
193            let (pw, pe) = prim(&g).unwrap();
194            assert_eq!(kw, pw);
195            assert_eq!(ke.len(), n - 1);
196            assert_eq!(pe.len(), n - 1);
197        }
198    }
199
200    #[test]
201    fn boglanmagan_grafda_none() {
202        let mut g = Graph::new_undirected(4);
203        g.add_edge(0, 1, 1);
204        g.add_edge(2, 3, 1);
205        assert!(kruskal(&g).is_none());
206        assert!(prim(&g).is_none());
207    }
208
209    #[test]
210    fn bitta_tugun() {
211        let g = Graph::new_undirected(1);
212        assert_eq!(kruskal(&g).unwrap(), (0, vec![]));
213        assert_eq!(prim(&g).unwrap(), (0, vec![]));
214    }
215
216    #[test]
217    fn mstda_sikl_yoq() {
218        let (_, qirralar) = kruskal(&namuna()).unwrap();
219        let mut ds = DisjointSet::new(7);
220        for (u, v, _) in qirralar {
221            assert!(ds.union(u, v), "MST da sikl bor!");
222        }
223        assert_eq!(ds.count(), 1);
224    }
225}
rust_algorithms/graph/mst.rs

rust_algorithms/graph/
mst.rs
