rust_algorithms/graph/mod.rs
1//! # Graflar (Graphs)
2//!
3//! Darslik: `08-graphs/`
4//!
5//! Graf — **tugunlar** (vertex) va ularni bog'lovchi **qirralar** (edge) to'plami.
6//! Yo'llar, ijtimoiy tarmoqlar, internet, bog'liqliklar — hammasi graf.
7//!
8//! ```text
9//! (0)───5───(1)
10//! │ ╲ │
11//! 2 7 3
12//! │ ╲ │
13//! (2)───1───(3)
14//! ```
15//!
16//! ## Ifodalash usullari
17//!
18//! | Usul | Xotira | "u–v qirra bormi?" | Qo'shnilarni sanash |
19//! |---|---|---|---|
20//! | Qo'shnilik ro'yxati (bu yerda) | O(V+E) | O(deg) | **O(deg)** |
21//! | Qo'shnilik matritsasi | O(V²) | **O(1)** | O(V) |
22//!
23//! Real graflarning aksariyati **siyrak** (E ≪ V²), shuning uchun ro'yxat afzal.
24//!
25//! ## Algoritmlarni tanlash
26//!
27//! ```text
28//! Eng qisqa yo'l kerakmi?
29//! ├── Qirralar og'irliksiz → bfs_shortest_path O(V+E)
30//! ├── Og'irliklar musbat → dijkstra O((V+E) log V)
31//! ├── Manfiy og'irlik bor → bellman_ford O(V·E)
32//! └── HAMMA juftlik orasida → floyd_warshall O(V³)
33//!
34//! Eng arzon bog'lovchi daraxt (MST)?
35//! ├── Siyrak graf → kruskal O(E log E)
36//! └── Zich graf → prim O(V²) / O(E log V)
37//!
38//! Tartib/bog'liqlik masalasi? → topological_sort O(V+E)
39//! ```
40
41mod core;
42mod mst;
43mod shortest_path;
44mod traversal;
45
46pub use core::{Edge, Graph};
47pub use mst::{kruskal, prim, MstResult};
48pub use shortest_path::{bellman_ford, bfs_shortest_path, dijkstra, dijkstra_path, floyd_warshall};
49pub use traversal::{
50 bfs, connected_components, dfs, dfs_recursive, has_cycle, is_bipartite, topological_sort,
51};