获取树中的最大节点数

Question

我想获得树中的最大节点数。所以下例中的最大节点数是 5，因为第一棵树中有 5 个节点。

示例输入如下； [['1 3'], ['1 4'], ['3 5'], ['4 6'], ['7 8']] 树变成了这样；

我已经编写了这段代码并且可以正常工作，但是是否可以编写更高效的代码？因为现在时间复杂度超过O(N²)。

function getMaxNumberOfNodes(edges) {
    let nodes = new Map();
    for (let i = 0; i < edges.length; i++) {
        let firstValue = parseInt(edges[i][0].charAt(0));
        let secondValue = parseInt(edges[i][0].charAt(2));

        if (nodes.has(firstValue)) {
            let tempArray = nodes.get(firstValue)
            tempArray.push(secondValue)
            nodes.set(firstValue, tempArray);
        }
        else {
            nodes.set(firstValue, [secondValue]);
        }
    }
    console.log(nodes) // Map(4) { 1 => [ 3, 4 ], 3 => [ 5 ], 4 => [ 6 ], 7 => [ 8 ] }
    let connectedNodes = new Map();
    for (let node of nodes.keys()) {
        let nodeValue = nodes.get(node);
        let tempArray = [];
        for (let i = 0; i < nodeValue.length; i++) {
            if (nodes.has(nodeValue[i])) {
                tempArray = tempArray.concat(nodes.get(nodeValue[i]));
            }
        }
        connectedNodes.set(node, nodes.get(node).concat(tempArray));
    }
    console.log(connectedNodes) // Map(4) { 1 => [ 3, 4, 5, 6 ], 3 => [ 5 ], 4 => [ 6 ], 7 => [ 8 ] }

    let maxNumberOfNodes = 0;

    for (let node of connectedNodes.keys()) {
        maxNumberOfNodes = Math.max(connectedNodes.get(node).length, maxNumberOfNodes);
    }
    return maxNumberOfNodes + 1;
}

console.log(getMaxNumberOfNodes([['1 3'], ['1 4'], ['3 5'], ['4 6'], ['7 8']])) // 5

Answer 1

在线性时间内找到所有根节点并 space（例如，通过构建一组所有节点和子节点）。然后，用DFS在线性时间内（O(V+E)，但E是V-1）测量每棵树的大小。

Answer 2

有点困惑，因为树数据结构最常见的是简单地记录当前有多少个节点，并根据需要递增和递减计数。（树通常包含其他类型的所谓“统计信息”。）

Answer 3

我会这样做：

let inputTest = [
  ['1 3'],
  ['1 4'],
  ['3 5'],
  ['4 6'],
  ['7 8']
];

function groupByRootNode(inp) {
  let root = new Map();
  let nodes = new Map();

  inp.forEach(pair => {
    let [prev, next] = pair[0].split(' ');
    //find the group either on the nodes map or the root map
    let group = nodes.get(prev) || root.get(prev);
    //check if the root node exists already
    let oldRoot = root.get(next);
    //if group doesn't exist
    if (!group) {
      //else group doesn't exist
      //we create a new tree group
      //prev is a new root node
      group = oldRoot || [];
      root.set(prev, group);
    }
    //add pair to existing group
    group.push(pair);
    //record new node as part of group
    nodes.set(next, group);

    if (oldRoot) {
      //if theres a root node with next, then that is no longer a root node
      root.delete(next);
    }
  });
  return root;
}

console.log(Array.from(groupByRootNode(inputTest),
  ([root, group]) => ({
    rootNode: root,
    nodes: group.length + 1
  })));

我认为这些评论是不言自明的。这只是通过公共根节点对“节点”进行分组。然后我只取出这些组的长度。 Map 结构确实隐藏了一些操作的复杂性。

编辑： 刚刚意识到，您需要最大树的节点数。在这一点上，我将其称为格式问题，因为您已经对节点进行了分组：

function largestTreeCount(nodes){
  let groups = groupByRootNode(nodes);
  let totalNodes = Array.from(groups, ([r, group]) => group.length+1);
  return Math.max(...totalNodes);
}

Answer 4

您可以构建一棵树，将所有节点作为对象中的参考，获取正面并计算嵌套尝试次数。最终取到最大值

const
    pairs = [[1, 3], [1, 4], [3, 5], [4, 6], [7, 8]],
    heads = new Set(pairs.map(([n]) => n)),
    references = {},
    count = nodes => nodes.reduce((s, n) => s + 1 + count(Object.keys(references[n])), 0);

pairs.forEach(([parent, child]) => {
    heads.delete(child);
    references[parent] = references[parent] || { };
    references[parent][child] = (references[child] = references[child] || { });
});

console.log(Math.max(...[...heads].map(n => count([n]))));
console.log(references);

.as-console-wrapper { max-height: 100% !important; top: 0; }

获取树中的最大节点数

Getting the maximum number of nodes in a tree

javascript

algorithm

tree

time-complexity

data-structures