如何使用固定颜色对树节点着色？

-1

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

来源

2015-09-04 user330612

你想每个相邻的节点是不同的颜色？父母不同于他们所有的孩子和兄弟姐妹彼此不同？随着颜色，否则随机分配？

旧的代码没有达到我对它的要求，所以我写了一个更好的代码版本，因为它是迭代的。我更满意的是，它满足了我上面所述的描述。

如果是，则与集合中的所有颜色C的开始时，挑一个父让调用一个P每个孩子从左到右颜色出来的一套C - {S,P}，其中S是颜色这个节点的左兄弟节点。对于每个设置为C - D的孩子重复此操作，其中D是此孩子的颜色，但您已选择该节点的颜色。

大多认为仍然是正确的，但不是深度优先递归我切换到迭代级别序遍历：

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

以下是格式化输出。请注意，没有孩子与其父母具有相同的颜色，也没有与左边的同一级别上的左兄弟姐妹或孩子具有相同的颜色。

<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种颜色着色（更多只是使它更加丰富多彩）。考虑：

这将是斑马条纹表的树等价物。特此我将此名称为斑马条纹树。

来源

2015-09-04 04:03:41

如何使用固定颜色对树节点着色？

回答

相关问题