Первый пример - это проблема обхода дерева : найти каждый путь, заданный корнем ко всем его листьям (узлам-потомкам, у которых нет дочерних элементов).
Чтобы выполнить обход, это помогает поместить дерево в форму, которая позволяет быстро искать детей по заданному родителю.После поиска нам нужно преобразовать полученные пути в запрошенный вами формат.
Вот дерево:
67
|
35
/ | \
3 37 33
/ \ \
5 39 1
\
7
Решение такое же, как в DFS / BFSза исключением того, что вместо возврата после того, как листовой узел найден, вычислите его путь обратно к корню, добавьте его в список основных путей и продолжайте поиск в остальной части дерева.
const pathsToLeaves = (root, tree) => {
const parent = {root: null};
const stack = [root];
const paths = [];
while (stack.length) {
let curr = stack.pop();
if (curr in tree) {
for (const child of tree[curr]) {
stack.push(child);
parent[child] = curr;
}
}
else {
const path = [];
while (curr) {
path.unshift(curr);
curr = parent[curr];
}
paths.push(path);
}
}
return paths;
};
const movesToTree = moves =>
moves.reduce((a, e) => {
if (!(e.from in a)) {
a[e.from] = [];
}
a[e.from].push(e.to);
return a;
}, {})
;
const pathsToMoves = paths =>
paths.map(f => f.reduce((a, e, i) => {
if (a === null) {
a = [{from: e}];
}
else if (i < f.length - 1) {
a[a.length-1].to = e;
a.push({from: e});
}
else {
a[a.length-1].to = e;
}
return a;
}, null))
;
const getPaths = (from, moves) =>
pathsToMoves(pathsToLeaves(from, movesToTree(moves)))
;
const moves = [
{from: 67, to: 35},
{from: 35, to: 3},
{from: 35, to: 37},
{from: 35, to: 33},
{from: 37, to: 5},
{from: 37, to: 39},
{from: 33, to: 1},
{from: 39, to: 7}
];
console.log(getPaths(67, moves));
Второй опубликованный вами пример - циклический мультиграф.Все еще возможно получить все запрошенные вами пути, но алгоритм намного менее эффективен, чем древовидная версия, из-за предварительной обработки для удаления параллельных ребер в мультиграфе, преобразования в / из желаемого формата и копирования массива / объекта во времяобход.Многие из этих ударов скорости могут быть оптимизированы с использованием различных подходов, но вот базовая версия:
const pathsFrom = (src, graph) => {
const stack = [[src, [], {}]];
const paths = [];
while (stack.length) {
const [curr, path, visited] = stack.pop();
if (curr in graph && !(curr in visited)) {
visited[curr] = 1;
path.push(curr);
let pathFollowed = false;
for (const neighbor of graph[curr]) {
if (!(neighbor in visited)) {
pathFollowed = true;
const visitedCpy = Object.keys(visited).reduce((a, e) => {
a[e] = visited[e];
return a;
}, {});
stack.push([neighbor, path.slice(0), visitedCpy]);
}
}
if (!pathFollowed) {
paths.push(path);
}
}
else {
paths.push(path.concat(curr));
}
}
return paths;
};
const movesToGraph = moves =>
moves.reduce((a, e) => {
if (!(e.from in a)) {
a[e.from] = [];
}
a[e.from].push(e.to);
return a;
}, {})
;
const pathsToMoves = paths =>
paths.map(f => f.reduce((a, e, i) => {
if (a === null) {
a = [{from: e}];
}
else if (i < f.length - 1) {
a[a.length-1].to = e;
a.push({from: e});
}
else {
a[a.length-1].to = e;
}
return a;
}, null))
;
const dedupe = a =>
Object.values(a.reduce((a, e) => {
const key = `${e.from} ${e.to}`;
if (!(key in a)) {
a[key] = e;
}
return a;
}, {}))
;
const getPaths = (from, moves) =>
pathsToMoves(pathsFrom(from, movesToGraph(dedupe(moves)), [], []))
;
[
[
{from: 67, to: 35},
{from: 35, to: 3},
{from: 35, to: 37},
{from: 35, to: 33},
{from: 37, to: 5},
{from: 37, to: 39},
{from: 33, to: 1},
{from: 39, to: 7}
],
[
{from: 84, to: 52},
{from: 52, to: 20},
{from: 52, to: 54},
{from: 52, to: 50},
{from: 20, to: 22},
{from: 20, to: 18},
{from: 54, to: 22},
{from: 50, to: 18},
{from: 22, to: 20},
{from: 18, to: 20},
{from: 20, to: 18},
{from: 20, to: 22},
]
].forEach(test => console.log(getPaths(test[0].from, test)));