Граф — структура данных из вершин (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) — уровень за уровнем, очередь. Кратчайший путь в невзвешенном графе