如何使用固定顏色對樹節點着色？

-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

如何使用固定顏色對樹節點着色？

回答

相關問題