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



@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.
Как именно реализовать такое при помощи рекурсии – бьюсь третий день, пока безрезультатно.

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


Решения вопроса 0


Ответы на вопрос 2



@wataru

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

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



@groog

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

Код

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());

В песочнице

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *