JavaScript — как проверить, есть ли в объекте циклические ссылки?

Question

[iSnaker]

Напоролся при собеседовании на такую задачу и не смог подойти к ней верно. Нужно определить, нет ли в указанном обьекте циклических зависимостей. В качестве ближайшего примера приводятся зависимости в node-модулях.
Итак, сама задача: написать функцию hasCircularDepengency(entrypoint, data), которая вернет true / false для объекта data =

const data = {
    "index.js" : ['foo.js'],
    "foo.js"   : ['baz.js', 'lol.js'],
    "baz.js"   : ['bar.js', 'lem.js'],
    "bar.js"   : ['baz.js', 'k.js'],
};

Функция вызывается с параметрами hasCircularDepengency("index.js",data) и по-идее должна вернуть false, так как указатель baz.js имеет зависимость bar.js, а bar.js - наоборот baz.js.
Алгоритм понятен - нужно составить список уже пройденных путей и если вдруг попадается указатель, который в списке оказался дважды - значит есть циклическая зависимость и результат будет false.
Как именно реализовать такое при помощи рекурсии - бьюсь третий день, пока безрезультатно.

Прошу помощи в разборе подхода.

Comments

[Lynn «Кофеман»]

Вернуть она, полагаю, должна true.

Answer 1

[Wataru]

Поиск в глубину.

Надо поддерживать список/множество уже посещенных вершин и пока посещаемых (те, что в стеке). При заходе в вершину в рекурсивной функции помещайте ее в множество пока посещаемых. При возвращении из функции перемещайте вершину в множество уже посещенных. В функции пройдитесь по всем ребрам, если они ведут в пока посещаемую вершину - вы нашли цикл. Если ребро ведет в уже посещенную - игнорируйте его. Если ребро ведет в не посещенную вершину - рекурсивно запускайтесь от нее.

Answer 2

[Даниил Попов]

Написал иллюстрацию, как такой обход организовать и посмотреть что происходит в каждый шаг. При желании и небольшом старании можете преобразовать функцию под условия задачи

Код

const data = {
  "index.js": ["foo.js"],
  "foo.js": ["baz.js", "lol.js"],
  "baz.js": ["bar.js", "lem.js"],
  "bar.js": ["baz.js", "k.js"]
};

function searchCircularDepengency(entry = "index.js", path = []) {
  const branch = data[entry];
  const newPath = [...path, entry];

  console.log("Path", newPath);

  // Если есть вложенные элементы,
  if (branch) {
    // проверить каждый
    branch.forEach((nextEntry) => {
      // на предмет прохожения ранее,
      if (path.includes(nextEntry)) {
        console.warn(
          "Found Circular Depengency " + nextEntry + " in " + entry,
          path
        );
        // если нет идти глубже
      } else {
        searchCircularDepengency(nextEntry, newPath);
      }
    });
  } else {
    console.log("Branch complite. All OK!");
  }
}

console.log(searchCircularDepengency());

В песочнице

Comments

[Wataru]

Ваше решение можно сильно ускорить, если не запускаться рекурсивно от ранее обработанных записей. Надо при выходе из функции пощать вершину в глобальный set и не запускаться от записей в нем.

Еще, вместо списка path стоит использовать set.

[iSnaker]

На данный момент у меня получилось вот такое решение на основе вашего. У него как минимум два минуса - в глобали хранится результат выполнения фунции + по условию задачи нужно в функцию передавать сам обьект, по которому производится поиск... Пока не придумал, как это обойти. Технически функция работает верно, но эти два момента меня смущают.

let hasDepengency = false;
// поиск циклических ссылок в объекте
const hasCircularDepengency = (entrypoint, path = new Set([])) => {

    const branch = data[entrypoint];
    const newPath = new Set([...path, entrypoint]);

    if (branch) {
        console.log("branch", branch, "path", newPath);

        for (let i = 0; i < branch.length; i++) {
            const nextEntry = branch[i];

            if (path.has(nextEntry)) {
                console.warn(`Circular depengency ${nextEntry} in ${entrypoint}`, path);
                hasDepengency = true;
                continue;
            } else {
                hasCircularDepengency(nextEntry, newPath);
            }
        }
    }

    return hasDepengency;
};

const data = {
    "index.js": ['foo.js', 'lol.js'],
    "foo.js": ['baz.js', 'lol.js'],
    "baz.js": ['bar.js', 'lem.js'],
    "bar.js": ['bazz.js', 'k.js'],
};

console.log(hasCircularDepengency('index.js'));

[Даниил Попов]

Wataru, вы правы во всем, кроме одного аспекта - это не решение, это примитивная функция для иллюстрации рекурсивного обхода дерева.

Как именно реализовать такое при помощи рекурсии - бьюсь третий день, пока безрезультатно.

Прошу помощи в разборе подхода.

Как я понимаю, помощь нужна была именно в организации рекурсии. Я привел пример, как это реализовать, но оставил автору возможность решить задачу самостоятельно.

Так же в данном контексте не вижу принципиальной разницы между обычным массивом и Set'ом. Раскройте, пожалуйста, мысль

[Wataru]

Даниил Попов,

Так же в данном контексте не вижу принципиальной разницы между обычным массивом и Set'ом. Раскройте, пожалуйста, мысль

Там проверка - есть ли данное имя в массиве. Она работает за линейную сложность и выполняется часто. Замена массива на Set заметно ускорит эту программу.

[Даниил Попов]

iSnaker, вы себя сильно ограничили одной функцией. Приведите код к следующему виду и тогда все необходимое можно держать в области видимости функции. Рекурсию делайте через checkBranch

function hasCircularDepengency(entrypoint, data) {
  let hasDepengency = false;
  //...
    checkBranch(/*...*/);
  //...
  return hasDepengency;
  function checkBranch(entry, path) {
    //...
  }
}

[Даниил Попов]

Wataru, кажется, я не совсем правильно вас понимаю. Так или иначе, от нас требуется проверка вхождения элемента в список. Независимо от инструмента этот поиск будет, но согласен, что Set значительно быстрее

Тест производительности