Module graph 

Graflar (Graphs)

Darslik: 08-graphs/

Graf — tugunlar (vertex) va ularni bog’lovchi qirralar (edge) to’plami. Yo’llar, ijtimoiy tarmoqlar, internet, bog’liqliklar — hammasi graf.

  (0)───5───(1)
   │  ╲      │
   2    7    3
   │      ╲  │
  (2)───1───(3)

Ifodalash usullari

Usul	Xotira	“u–v qirra bormi?”	Qo’shnilarni sanash
Qo’shnilik ro’yxati (bu yerda)	O(V+E)	O(deg)	O(deg)
Qo’shnilik matritsasi	O(V²)	O(1)	O(V)

Real graflarning aksariyati siyrak (E ≪ V²), shuning uchun ro’yxat afzal.

Algoritmlarni tanlash

Eng qisqa yo'l kerakmi?
 ├── Qirralar og'irliksiz        → bfs_shortest_path   O(V+E)
 ├── Og'irliklar musbat          → dijkstra            O((V+E) log V)
 ├── Manfiy og'irlik bor         → bellman_ford        O(V·E)
 └── HAMMA juftlik orasida       → floyd_warshall      O(V³)

Eng arzon bog'lovchi daraxt (MST)?
 ├── Siyrak graf                 → kruskal             O(E log E)
 └── Zich graf                   → prim                O(V²) / O(E log V)

Tartib/bog'liqlik masalasi?      → topological_sort    O(V+E)

Structs

Edge

Qirra: qayerga va qancha “narx” bilan.

Graph

Qo’shnilik ro’yxati (adjacency list) asosidagi graf.

Functions

bellman_ford

Bellman-Ford — manfiy og’irliklar bilan ham ishlaydi va manfiy siklni aniqlaydi.

bfs

BFS (Breadth-First Search) — kenglikka qidiruv: to’lqin kabi tarqaladi.

bfs_shortest_path

Og’irliksiz grafda eng qisqa yo’l — oddiy BFS.

connected_components

Bog’liq komponentalar: bir-biriga yetib bo’ladigan tugunlar guruhlari.

dfs

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

dfs_recursive

DFS ning rekursiv ko’rinishi — g’oyani ko’rsatish uchun.

dijkstra

Dijkstra — musbat og’irlikli grafda bitta manbadan barcha tugunlargacha eng qisqa masofalar.

dijkstra_path

Dijkstra + yo’lni tiklash: start dan goal gacha (narx, yo'l).

floyd_warshall

Floyd-Warshall — barcha juftliklar orasidagi eng qisqa masofalar.

has_cycle

Grafda sikl bormi?

is_bipartite

Graf ikki bo’lakli (bipartite) mi? — tugunlarni 2 rangga bo’yash mumkinmi, shundayki qo’shnilar har doim turli rangda bo’lsin.

kruskal

Kruskal — qirralarni arzonidan boshlab tanlash (ochko’z algoritm).

prim

Prim — daraxtni bitta tugundan boshlab “o’stirish”.

topological_sort

Topologik saralash — yo’naltirilgan asiklik grafda (DAG) bog’liqliklar tartibi.

Type Aliases

MstResult

MST natijasi: (umumiy og'irlik, tanlangan qirralar).