Пройдите по дереву по глубине, а не по веткам

2020-08-01 javascript arrays breadth-first-search tree-traversal

У меня есть большой массив объектов, таких как {id, followers} где followers повторяют шаблон:

{
  id: 0, followers: [{
    id: 1, followers: [{
      id: 11, followers: [{
        id: 111, followers: [...]
      }]
    }]
  }, {
    id: 2, followers: [{
      id: 21, followers: [{
        id: 211, followers: [...]
      }]
    }]
  }, {
    id: 3, followers: [{
      id: 31, followers: [...]
    }]
  }, ...]
}

Я хочу пройти по этому дереву и создать плоский массив типа {id, depth}

Я использую следующую рекурсивную функцию:

function recurse(user, depth = 0, list = []) {
  for (const { id } of user.followers) {
    list.push({ id, depth });
  }
  for (const follower of user.followers) {
    recurse(
      user: follower,
      depth: depth + 1,
      list
    );
  }
  return list;
}

Он проникает все глубже и глубже в каждую ветку, прежде чем двигаться дальше, что приводит к чему-то вроде

[
  { id: 0, depth: 0},
  { id: 1, depth: 1},
  { id: 11, depth: 2},
  { id: 111, depth: 3},
  { id: 1111, depth: 4},
  { id: 11111, depth: 5},
  ...
  { id: 2, depth: 1},
  { id: 21, depth: 2},
  { id: 211, depth: 3},
  ...
  { id: 3, depth: 1},
  { id: 31, depth: 2},
  { id: 311, depth: 3},
  ...
]

Но я хочу, чтобы это автоматически получалось отсортированным по глубине, например:

[
  { id: 0, depth: 0},
  { id: 1, depth: 1},
  { id: 2, depth: 1},
  { id: 3, depth: 1},
  { id: 4, depth: 1},
  ...
  { id: 11, depth: 2},
  { id: 12, depth: 2},
  { id: 13, depth: 2},
  ...
  { id: 111, depth: 3},
  { id: 211, depth: 3},
  ...
]

Я хочу пройти элементы по глубине, то есть все элементы с глубины 0, затем все элементы с глубины 1 и так далее.

Моя реализация не соблюдает порядок глубины. Он просто следует за ветвями так глубоко, как они идут сначала, а затем переходит к следующей ветке.

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

Как я могу пройти по этому дереву по глубине, а не по веткам?

Answers

Я не думаю, что обход массива с использованием подхода «сначала в глубину» решит ваши проблемы, потому что:

  1. Это по-прежнему не предотвратит дублирование.
  2. Я не думаю, что разумно предполагать, что идентификатор 111 не будет в первой ветке, где в вашем примере сосредоточены все остальные идентификаторы на основе 1.

Приведенная ниже функция выполняет действительно глубокий поиск. Также он обрабатывает корневой элемент, который не обрабатывается в примере OP:

function traverse(user = {}, depth = 0, map = new Map()) {
  const { id, followers } = user;
  if (id != null && !map.has(id)) {
    map.set(id, { id, depth });
  }
  if (followers) {
    const [first, ...rest] = followers;
    traverse(first, depth + 1, map);
    for (const user of rest) {
      traverse(user, depth + 1, map);
    }
  }
  return map;
}

const resultMap = traverse(input);
const sortedResult = Array.from(resultMap).sort(([, a], [, b]) => a.depth - b.depth);

Нашел решение. По-видимому, это Breadth-first_search и требует поддержки очереди:

function traverse(user) {
  const queue = [];
  const list = [];
  queue.push({ followers: user.followers, depth: 0 });

  let item;
  while (item = queue.shift()) {
    const { followers, depth } = item;
    for (const follower of followers) {
      if (list.find(l => l.id === follower.id)) continue;
      list.push({ id: follower.id, depth });
      queue.push({ followers: follower.followers, depth: depth + 1 });
    }
  }

  return list;
}

Related