Пройдите по дереву по глубине, а не по веткам - PullRequest
Новая
       71

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

0 голосов
/ 01 августа 2020

У меня есть глубокий массив объектов, таких как {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},
  ...
]

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

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

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

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

Ответы [ 2 ]

0 голосов
/ 01 августа 2020

Нашел решение. По-видимому, это 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;
}
0 голосов
/ 01 августа 2020

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

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

Функция ниже сначала выполняет действительно глубину поиск. Также он обрабатывает элемент root, который не обрабатывается в примере 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);
...