Дан граф с entry point-нодой — как алгоритмически собрать вокруг неё релевантное поддерево?

Построение поддерева от entry point

Задача состоит в том, чтобы из произвольного графа выделить подграф, достижимый из заданной вершины (entry point). Это классическая задача обхода графа, которая решается алгоритмами DFS (Depth-First Search) или BFS (Breadth-First Search).

Алгоритм DFS (рекурсивный)

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

function buildSubtree(node, graph, visited = new Set()) {
  if (visited.has(node)) return null;
  visited.add(node);
  const subtree = { value: node, children: [] };
  for (const neighbor of graph[node]) {
    const child = buildSubtree(neighbor, graph, visited);
    if (child) subtree.children.push(child);
  }
  return subtree;
}

Алгоритм BFS (итеративный)

BFS обходит граф по уровням, используя очередь. Он подходит для широких графов и гарантирует кратчайший путь, но для построения поддерева требуется хранить родительские связи.

function buildSubtreeBFS(start, graph) {
  const visited = new Set();
  const queue = [start];
  const tree = { value: start, children: [] };
  const parentMap = new Map();
  parentMap.set(start, tree);
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        const childNode = { value: neighbor, children: [] };
        parentMap.get(node).children.push(childNode);
        parentMap.set(neighbor, childNode);
        queue.push(neighbor);
      }
    }
  }
  return tree;
}

Вывод

Выбор между DFS и BFS зависит от структуры графа: для глубоких деревьев с редкими ветвлениями эффективнее DFS, для широких графов с большим количеством соседей — BFS. Оба алгоритма корректно собирают поддерево, если граф не содержит циклов; при наличии циклов необходимо отслеживать посещённые вершины, чтобы избежать зацикливания.