Qrafın təmsili
Qraf iki şeydən ibarətdir: vertex-lər (təpələr, node-lar) və onları birləşdirən edge-lər (tillər). Bütün qalan detallar bu ikisinin üzərinə qurulur.
Qrafın üç əsas xüsusiyyəti var və məsələni oxuyan kimi hər üçünü müəyyən etməlisən:
- Directed vs undirected — edge tək istiqamətlidirmi? Twitter-də "follow" directed-dir (sən onu izləyirsən, o səni yox), Facebook-da "dostluq" undirected-dir
- Weighted vs unweighted — edge-in qiyməti varmı? Yol xəritəsində məsafə/vaxt weight-dir, sadə tanışlıq qrafında weight yoxdur
- Cycle var, yoxsa yox — cycle olmayan directed qraf DAG adlanır və bu, tapşırıq asılılıqları, build sistemləri, migration sıralaması üçün əsas modeldir
Ölçü işarələri: V — vertex sayı, E — edge sayı. Qrafın sıxlığı (density) da vacibdir: E ≈ V olanda qraf sparse, E ≈ V² olanda dense sayılır. Real dünyada qrafların böyük əksəriyyəti sparse-dir.
Qrafı yaddaşda saxlamağın iki standart yolu var.
Adjacency list — hər vertex üçün onun qonşularının siyahısı. Praktikada Map<vertex, qonşular> və ya massiv-massivi kimi saxlanılır. Yaddaş O(V + E). Sparse qraflarda default seçim budur — real məsələlərin 90 faizində məhz bunu yazacaqsan.
Adjacency matrix — V × V ölçülü cədvəl, matrix[u][v] iki vertex arasında edge olub-olmadığını (və ya onun weight-ini) göstərir. Yaddaş O(V²) — burada edge sayı ümumiyyətlə rol oynamır: 10 000 vertex-li qrafda cəmi 3 edge olsa belə, 100 milyon xana ayrılır.
Seçim qaydası bir cümlə ilə: "Bu edge var?" sualını çox verirsənsə və qraf kiçik/dense-dirsə → matrix; qonşuları gəzirsənsə və qraf böyük/sparse-dirsə → list.
| Əməliyyat | Adjacency list | Adjacency matrix |
|---|---|---|
| Yaddaş | O(V + E) | O(V²) — edge sayından asılı deyil |
| Edge əlavə etmək | O(1) | O(1) |
| "u–v edge-i var?" yoxlaması | O(deg(u)) — qonşuları gəzmək lazımdır | O(1) — birbaşa indeks |
| u-nun bütün qonşularını gəzmək | O(deg(u)) — optimal | O(V) — bütün sətri oxumaq lazımdır |
| Edge silmək | O(deg(u)) | O(1) |
| Nə vaxt qalib gəlir | Sparse qraflar, BFS/DFS, real şəbəkələr | Kiçik və dense qraflar, tez-tez edge yoxlaması, matris alqoritmləri (Floyd-Warshall) |
Ən çətin hissə qraf alqoritmini bilmək deyil — məsələnin qraf olduğunu görməkdir. Bunlar hamısı qrafdır:
- Sosial şəbəkə — vertex = istifadəçi, edge = dostluq/follow; "iki nəfər arasında neçə addım var" sualı BFS-dir
- Marşrutlaşdırma — vertex = kəsişmə, edge = yol seqmenti, weight = vaxt; ən qısa yol Dijkstra-dır
- Asılılıq qrafı — vertex = modul/tapşırıq, edge = "əvvəl bu bitməlidir"; qurulma sırası topological sort, dairəvi asılılıq isə cycle detection-dır
- Şəkil / oyun lövhəsi / labirint — hər xana bir vertex, qonşu xanalar edge; heç bir
Graphsinfi yazmağa ehtiyac yoxdur, qonşuları[[0,1],[1,0],[0,-1],[-1,0]]ilə hesablayırsan - Vəziyyət qrafı — vertex = sistemin vəziyyəti, edge = keçid; "minimum neçə addımda A vəziyyətindən B-yə çatmaq olar" yenə BFS-dir
Sonuncu ikisi interview-da ən çox buraxılan haldır: namizəd "bu matris məsələsidir" deyib əl ilə döngə yazmağa başlayır, halbuki bu, gizlədilmiş qraf məsələsidir.
Interview məsləhəti: qraf məsələsində koda başlamazdan əvvəl dörd sualı ucadan ver — directed-dir? weight var? cycle ola bilər? V və E təxminən nə qədərdir? Sonra seçimini əsaslandır: "V 10⁵-ə qədər, E isə V-yə yaxındır, yəni sparse — adjacency list götürürəm, matrix 10¹⁰ xana istəyərdi." Bu bir cümlə səni "alqoritmi əzbərləmiş" namizəddən "resursları düşünən" namizədə çevirir.