查找每个级别/高度的树的宽度(非二叉树)

Question

亲爱的经验丰富的朋友们，我正在寻找一种算法(Python)，它可以在每个级别输出树的宽度。以下是输入和预期输出。

(我用一个更复杂的边列表更新了这个问题。原来的边列表排序问题可以通过@Samwise答案优雅地解决。)

---

输入(边缘列表：源-->目标)

[[11,1],[11,2],
[10,11],[10,22],[10,33],
[33,3],[33,4],[33,5],[33,6]]

树状图如下：

10
/   |  
11   22  33
/     / |  
1   2  3  4  5 6

预期输出(每层宽度/高度)

[1,3,6] # according to the width of level 0,1,2

---

我浏览过网页。这个主题似乎与BFS和级别顺序遍历有关。然而，大多数解决方案都是基于二叉树的。当树不是二进制的(例如上述情况)时，如何解决问题？

(我是算法的新手，任何参考资料都将不胜感激。谢谢！)

Answer 1

构建一个"电平"；每个节点的，然后计算每个级别的节点数：

>>> from collections import Counter
>>> def tree_width(edges):
...     levels = {}  # {node: level}
...     for [p, c] in edges:
...         levels[c] = levels.setdefault(p, 0) + 1
...     widths = Counter(levels.values())  # {level: width}
...     return [widths[level] for level in sorted(widths)]
...
>>> tree_width([[0,1],[0,2],[0,3],
... [1,4],[1,5],
... [3,6],[3,7],[3,8],[3,9]])
[1, 3, 6]

Answer 2

这可能不是最有效的，但它只需要在边缘列表上进行两次扫描，因此在恒定因子下是最佳的。它不要求边列表中的边的顺序，但坚持每个边都是(source，dest)。此外，不要检查边列表是否描述了一个连接的树(或者一棵树；如果边列表是循环的，程序将永远不会终止)。

from collections import defauiltdict
# Turn the edge list into a (non-binary) tree, represented as a
# dictionary whose keys are the source nodes with the list of children
# as its value.
def edge_list_to_tree(edges):
'''Given a list of (source, dest) pairs, constructs a tree.
Returns a tuple (tree, root) where root is the root node
and tree is a dict which maps each node to a list of its children.
(Leaves are not present as keys in the dictionary.)
''' 
tree = defaultdict(list)
sources = set()  # nodes used as sources
dests = set()    # nodes used as destinations
for source, dest in edges:
tree[source].append(dest)
sources.add(source)
dests.add(dest)
roots = sources - dests      # Source nodes which are not destinations
assert(len(roots) == 1)      # There is only one in a tree
tree.default_factory = None  # Defang the defaultdict
return tree, roots.pop()
# A simple breadth-first-search, keeping the count of nodes at each level.
def level_widths(tree, root):
'''Does a BFS of tree starting at root counting nodes at each level.
Returns a list of counts.
'''
widths = []         # Widths of the levels
fringe = [root]     # List of nodes at current level
while fringe:
widths.append(len(fringe))
kids = []       # List of nodes at next level
for parent in fringe:
if parent in tree:
for kid in tree[parent]:
kids.append(kid)
fringe = kids   # For next iteration, use this level's kids
return widths
# Put the two pieces together.
def tree_width(edges):
return level_widths(*edge_list_to_tree(edges))

Answer 3

基于宽度优先遍历的可能解决方案在Width First Traversal中，我们将节点添加到数组中，但在该解决方案中，我们会将数组及其级别一起放入对象中，然后将其添加到数组。

function levelWidth(root) {
const counter = [];
const traverseBF = fn => {
const arr = [{n: root, l:0}];
const pushToArr = l => n => arr.push({n, l});
while (arr.length) {
const node = arr.shift();
node.n.children.forEach(pushToArr(node.l+1));
fn(node);
}
};    
traverseBF(node => {
counter[node.l] = (+counter[node.l] || 0) + 1;
});
return counter;
}