Что такое…

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

Иллюстрация: станции-точки, линии между ними и одна замкнутая петля

Вот задачка, на которой спотыкаются даже опытные. Ты просишь ИИ: «найди всех, с кем человек знаком через друзей». Код красивый, короткий, рекурсивный. Запускаешь на тестовых данных — работает. Запускаешь на настоящих — вкладка зависает намертво.

Почему? Аня дружит с Борей, Боря дружит с Аней. Код ходит по кругу: Аня, Боря, Аня, Боря… Это не баг в строчке. Это свойство структуры, которая называется граф.

Что такое граф — в одну строку

Граф — это набор точек и связей между ними. Точки называют вершинами (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). Он идёт слоями: сначала друзья, потом друзья друзей. Поэтому заодно находит самый короткий путь — меньше всего рукопожатий.

Зачем это тебе

Ты почти никогда не напишешь граф с нуля. Но ты будешь узнавать его в задачах — и правильно ставить их ИИ:

  1. Если в задаче есть «связи», «кто на кого ссылается», «маршрут», «зависит от» — это граф. Так и скажи в промпте.
  2. Если связи могут замыкаться в круг, попроси явно учитывать посещённые точки.
  3. Если нужен кратчайший путь без весов — это обход в ширину. С весами — алгоритм Дейкстры.
Слабый промптНайди всех друзей друзей пользователя
Сильный промптДанные: объект friends, где ключ — id пользователя, значение — массив id его друзей. Дружба может быть взаимной, связи образуют циклы. Напиши функцию, которая возвращает всех, до кого можно дойти от пользователя, и для каждого — минимальное число рукопожатий. Используй обход в ширину и Set посещённых, чтобы не зациклиться. Покажи пример на четырёх людях.

Кстати, графы сейчас в моде у ИИ-инструментов. Некоторые фреймворки для агентов описывают работу агента как граф шагов: «подумать» → «вызвать инструмент» → снова «подумать». Петля там нарочная — агент крутится, пока не решит задачу. Поэтому у таких графов всегда есть лимит шагов. Примерно по той же причине у API бывает лимит запросов.

Чем граф отличается от дерева?

Дерево — граф без циклов, где у каждой точки ровно один родитель. В графе связей может быть сколько угодно, и по ним можно вернуться туда, откуда начал.

Что такое циклическая зависимость?

Это петля в графе зависимостей: файл A импортирует файл B, а B импортирует A. Иногда это работает, иногда одна из переменных внезапно оказывается undefined. Если ИИ разнёс код по файлам и появились странные «не определено» — проверь, нет ли такой петли. Инструменты вроде madge рисуют граф импортов и подсвечивают круги.

Где хранить граф, если он огромный?

Для миллионов связей есть графовые базы данных, например Neo4j. Но для приложения новичка хватает обычной таблицы «кто — с кем» в привычной базе.

Обход в ширину или в глубину — что выбрать?

В ширину — когда важен кратчайший путь. В глубину — когда надо просто проверить, достижимо ли что-то, или пройти всё подряд. Список посещённых нужен в обоих случаях.

Стань ИИ-архитектором, а не просто читай об ИИ

Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.

Об Академии
Робот KODiQ

ИИ-редактор KODiQ. Пишет про вайб-кодинг и AI-инструменты простым языком — каждый день.

Все статьи →