Как получить количество ссылок на свойство объекта javascript

Question

У меня есть эти данные:

const main = 'test1';
const data = [
  {
    from: 'test1',
    to: 'test2'
  },
  {
    from: 'test2',
    to: 'test3'
  },
  {
    from: 'test3',
    to: 'test4'
  },
  {
    from: 'test4',
    to: 'test2'
  },
  {
    from: 'test1',
    to: 'test4'
  }
];

Я хочу получить количество ссылок на главный узел (в данном случае test1 ). Например, если мы посмотрим на узел test3 , потребуется 2 ссылки, чтобы добраться до test1 :

test3 → test2 → test1

То же самое с узлом test2 , для получения test1 требуется 1 ссылка.

Какой лучший способ рассчитать это? В конце я хочу получить самое длинное количество ссылок на test1 . В нашем примере это 3:

test3 → test2 → test4 → test1

Answer 1

Вам нужно будет посетить каждый возможный путь. Однако если цикл встречается и целевой узел достижим, то самое длинное расстояние становится бесконечным, так как этот цикл можно проходить любое количество раз.

Чтобы посетить все пути, вы можете использовать рекурсивную функцию.

Вот один из них:

function find(data, sourceName, targetName) {
    // Create hash data structure keying nodes by their name
    const map = new Map(data.map(({from}) => [from, []]));
    data.forEach(({from,to}) => map.get(from).push(map.get(to)));
    // If links are supposed to be undirected, allowing traversal in both directions
    //   then uncomment this:
    // data.forEach(({from,to}) => map.get(to).push(map.get(from)));
    const target = map.get(targetName);
    // Recursive function
    function recur(node) {
        if (node === target) return 0; // Found target
        if (node.visited) { // Cycle; mark node for detection during backtracking 
            node.onCycle = true;
            return -Infinity;
        }
        node.visited = true;
        let dist = 1 + Math.max(...node.map(recur)); // Maximise path length
        node.visited = false;
        // Leave out next line if longest path should not include cycles
        if (node.onCycle && dist > 0) return Infinity; // Solution path can have cycles
        return dist;
    }
    const dist = recur(map.get(sourceName)); // Start!
    return dist < 0 ? null : dist; // Return null when target cannot be reached
}

const data = [{from: 'test1', to: 'test2'},{from: 'test2', to: 'test3'},{from: 'test3',to: 'test4'},{from: 'test4',to: 'test2'},{from: 'test1',to:'test4'}];
const longestDist = find(data, 'test1', 'test3');
console.log(longestDist);

Обратите внимание, что это решение не продолжит поиск, проходящий через целевой узел, а затем снова попытается найти его оттуда (через цикл). Другими словами, предполагается, что путь может содержать только цель в качестве своего последнего узла, а не несколько раз.

Если вы хотите исключить пути с циклами, удалите строку, которая возвращает Infinity как расстояние.

В коде предполагается, что ссылки направлены . В случае, если ссылки следует понимать как двунаправленные (также известные как unirected ), это означает, что если указано одно направление, противоположное направление также возможно без явного включения его в качестве зеркальной ссылки, затем раскомментируйте второе forEach строка в приведенном выше коде.

Answer 2

Ваш вопрос может быть переопределен в терминах теории графов: "test1", "test2", ... являются вершинами, массив данных содержит ребра (пары "от-до") - поэтому у нас есть график - поиск самого длинного пути в графе NP-сложная проблема - wiki . Поэтому вам нужно проверить все возможные пути, чтобы найти самый длинный