@iSnaker
Итак, сама задача: написать функцию 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());