Граф — структура даних із вершинами (nodes) і ребрами (edges) між ними. Моделює будь-які зв'язки: соцмережі, дорожні карти, залежності пакетів, мікросервіси.
Типи графів
Directed / Undirected — ребра спрямовані (A→B) чи ні (A—B)
Weighted — ребра мають вагу (відстань, вартість)
Cyclic / Acyclic — є цикли чи ні
DAG (Directed Acyclic Graph) — спрямований без циклів. Граф залежностей npm/composer
Представлення
Adjacency Matrix — 2D масив. O(1) перевірка ребра, O(V²) пам'ять
Adjacency List — список сусідів. O(V+E) пам'ять, зазвичай ефективніший
Алгоритми обходу
BFS (Breadth-First Search) — рівень за рівнем, черга. Найкоротший шлях в незваженому графі
DFS (Depth-First Search) — в глибину, стек. Виявлення циклів, топологічне сортування