如何使用固定的颜色集为树节点着色？

Question

我有一个员工层次结构树，我想为其应用颜色。我最多只能使用 10 种颜色，因为更多的颜色会让用户感到困惑。我可以使用什么逻辑或算法来用一组颜色为树着色？有一些技巧可以做到这一点吗？我最初的想法是通过 BFS 找到树中的 10 个子树，然后对它们进行不同的着色。如果第一层本身有 >10 children，则不应用任何颜色，如果有 < 10 个节点，则继续向下直到我们找到 10 个要着色的子树。这是看待这个问题的正确方法吗？我有更多想法吗？

Answer 1

你想让每一个相邻的节点都是不同的颜色吗？ Parents 不同于他们所有的 child 人和兄弟姐妹彼此不同？使用随机分配的颜色？

旧代码不符合我提出的要求，所以我编写了一个新版本的代码，由于它是迭代的，所以要好得多。而且我更满意它所做的符合我上面所说的描述。

If so then start out with the set of all colors C, pick one for the parent lets call that one P for each of the children going left to right color them out of the set C - {S,P} where S is the color of the left sibling of this node. Repeat this for each of the children with the set C - D where D is the color of this child except that you have already picked the color of the node.

大部分仍然正确，但我切换到迭代级别顺序遍历而不是深度优先递归：

import random

class Node(object):

    def __init__(self, children):
        self.children = children
        self.color = None

    def __str__(self):
        return  '<node {}>'.format(self.color) + ' '.join(str(c) for c in self.children) + '</node>'

def pick(s):
    return random.choice(list(s))

def assign_colors(node, set_of_colors):

    node.color = pick(set_of_colors)

    level = [node]
    while level:

        left_sibling = set()
        _level = []
        for node in level:
            for child in node.children:
                _level.append(child)
                child.color = pick(set_of_colors - (set([node.color]) | left_sibling))
                left_sibling = set([child.color])

        level = _level

test = Node([Node([Node([Node([]), Node([]), Node([]), Node([])]),
             Node([Node([]), Node([])]), Node([]), Node([])]),
             Node([Node([]), Node([]), Node([]), Node([])]), Node([])])

assign_colors(test, set([1,2,3,4]))

print test

assign_colors(test, set([1,2,3,4,5]))

print test

以下是重新格式化后的输出。请注意，没有 child 与其 parent 具有相同的颜色，也没有与其左侧同一级别的左兄弟或 child 相同的颜色。

<node 3>
    <node 4>
        <node 2>
            <node 4></node>
            <node 1></node>
            <node 4></node>
            <node 1></node>
        </node>
        <node 1>
            <node 4></node>
            <node 3></node>
        </node>
        <node 3></node>
        <node 1></node>
    </node>
    <node 1>
        <node 2></node>
        <node 3></node>
        <node 2></node>
        <node 4></node>
    </node>
    <node 2></node>
</node>
<node 4>
    <node 2>
        <node 1>
            <node 5></node>
            <node 4></node>
            <node 2></node>
            <node 4></node>
        </node>
        <node 5>
            <node 3></node>
            <node 2></node>
        </node>
        <node 4></node>
        <node 3></node>
    </node>
    <node 5>
        <node 1></node>
        <node 4></node>
        <node 2></node>
        <node 3></node>
    </node>
    <node 1></node>
</node>

任何一棵树最多只能用 3 种颜色着色（越多颜色越多）。考虑：

那将是斑马条纹表的树等效项。在此我将这棵树命名为斑马条纹树.

如何使用固定的颜色集为树节点着色？

How to color tree nodes with fixed set of colors?

tree