Определение наличия циклических зависимостей в графе файлов

Условие

Реализуйте функцию hasCircularDependency, которая проверяет, присутствует ли цикл в графе зависимостей между файлами.

type Resource = string;
type Vector = Record<Resource, Resource[]>;

function hasCircularDependency(entrypoint: Resource, deps: Vector): boolean {
  // ваш код тут
}

// пример
console.warn(hasCircularDependency('index.js', {
  'index.js': ['foo.js', 'bar.js'],
  'bar.js': ['baz.js'],
  'foo.js': ['baz.js'],
  'baz.js': ['x.js'],
  'x.js': ['foo.js'] // цикл: index → foo → baz → x → foo
})); // true

Ответ

Используйте DFS с двумя множествами: активный стек пути и уже завершённые вершины. Ребро в активную вершину означает цикл, а повторный заход в завершённую — нет.

function hasCircularDependency(entrypoint: Resource, deps: Vector): boolean {
  const active = new Set<Resource>();
  const done = new Set<Resource>();
  function visit(file: Resource): boolean {
    if (active.has(file)) return true;
    if (done.has(file)) return false;
    active.add(file);
    for (const dependency of Object.hasOwn(deps, file) ? deps[file] : []) {
      if (visit(dependency)) return true;
    }
    active.delete(file);
    done.add(file);
    return false;
  }
  return visit(entrypoint);
}

Проверяются только вершины, достижимые из entrypoint. Отсутствующий ключ означает файл без известных зависимостей. В примере цикл foo → baz → x → foo найден. Время O(V+E), память O(V); для очень глубокого графа замените рекурсию явным стеком.