Что такое граф в программировании — и почему обход графа может зависнуть навсегда

Вот задачка, на которой спотыкаются даже опытные. Ты просишь ИИ: «найди всех, с кем человек знаком через друзей». Код красивый, короткий, рекурсивный. Запускаешь на тестовых данных — работает. Запускаешь на настоящих — вкладка зависает намертво.
Почему? Аня дружит с Борей, Боря дружит с Аней. Код ходит по кругу: Аня, Боря, Аня, Боря… Это не баг в строчке. Это свойство структуры, которая называется граф.
Что такое граф — в одну строку
Граф — это набор точек и связей между ними. Точки называют вершинами (nodes), связи — рёбрами (edges). Всё.
Звучит как школьная математика, но графы повсюду:
- Соцсеть. Люди — точки, дружба — связь.
- Карта. Перекрёстки — точки, дороги — связи. У каждой дороги есть длина.
- Зависимости проекта. Пакеты — точки, «пакет A требует пакет B» — связь. Когда менеджер пакетов ставит библиотеки, он обходит именно граф.
- Ссылки в интернете. Страницы — точки, ссылки — связи. Поисковики так и обходят сеть.
Какие бывают графы
Графы отличаются по двум простым признакам.
Направленный или нет. Дружба обычно взаимная — связь без стрелки. А подписка в соцсети — со стрелкой: ты подписан на автора, он на тебя нет. Зависимости пакетов тоже со стрелкой.
С весом или без. Если у связи есть «цена» — длина дороги, время в пути — граф взвешенный. Навигатор ищет путь с минимальной суммой весов, а не с минимумом поворотов.
И главное отличие от дерева — например, от дерева папок на твоём компьютере. В дереве у каждой папки один родитель, и по кругу не пройти. В графе — можно. Дерево — это частный случай графа без петель.
Как граф выглядит в коде
Чаще всего — как объект, где у каждой точки список соседей. Это называется «список смежности»:
const friends = {
anya: ["borya", "vika"],
borya: ["anya"],
vika: ["anya", "gleb"],
gleb: ["vika"],
};
Теперь обход «всех знакомых через друзей». Секрет — список уже посещённых:
function everyoneReachable(start) {
const seen = new Set([start]);
const queue = [start];
while (queue.length > 0) {
const person = queue.shift();
for (const next of friends[person]) {
if (!seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
return seen;
}
Строчка if (!seen.has(next)) — та самая, которой не хватало в зависшем коде. Без неё Аня и Боря гоняли бы друг друга по кругу вечно.
Такой обход называется «в ширину» (BFS). Он идёт слоями: сначала друзья, потом друзья друзей. Поэтому заодно находит самый короткий путь — меньше всего рукопожатий.
Зачем это тебе
Ты почти никогда не напишешь граф с нуля. Но ты будешь узнавать его в задачах — и правильно ставить их ИИ:
- Если в задаче есть «связи», «кто на кого ссылается», «маршрут», «зависит от» — это граф. Так и скажи в промпте.
- Если связи могут замыкаться в круг, попроси явно учитывать посещённые точки.
- Если нужен кратчайший путь без весов — это обход в ширину. С весами — алгоритм Дейкстры.
Найди всех друзей друзей пользователяДанные: объект friends, где ключ — id пользователя, значение — массив id его друзей. Дружба может быть взаимной, связи образуют циклы. Напиши функцию, которая возвращает всех, до кого можно дойти от пользователя, и для каждого — минимальное число рукопожатий. Используй обход в ширину и Set посещённых, чтобы не зациклиться. Покажи пример на четырёх людях.Кстати, графы сейчас в моде у ИИ-инструментов. Некоторые фреймворки для агентов описывают работу агента как граф шагов: «подумать» → «вызвать инструмент» → снова «подумать». Петля там нарочная — агент крутится, пока не решит задачу. Поэтому у таких графов всегда есть лимит шагов. Примерно по той же причине у API бывает лимит запросов.
Чем граф отличается от дерева?
Дерево — граф без циклов, где у каждой точки ровно один родитель. В графе связей может быть сколько угодно, и по ним можно вернуться туда, откуда начал.
Что такое циклическая зависимость?
Это петля в графе зависимостей: файл A импортирует файл B, а B импортирует A. Иногда это работает, иногда одна из переменных внезапно оказывается undefined. Если ИИ разнёс код по файлам и появились странные «не определено» — проверь, нет ли такой петли. Инструменты вроде madge рисуют граф импортов и подсвечивают круги.
Где хранить граф, если он огромный?
Для миллионов связей есть графовые базы данных, например Neo4j. Но для приложения новичка хватает обычной таблицы «кто — с кем» в привычной базе.
Обход в ширину или в глубину — что выбрать?
В ширину — когда важен кратчайший путь. В глубину — когда надо просто проверить, достижимо ли что-то, или пройти всё подряд. Список посещённых нужен в обоих случаях.
Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.





