2016-11-17 16 views
0

代码:使用BFS着色算法来检查是否图形在Python是二分

def bipartite(G): 
    open_list = [1] 
    colors = {} 
    color_counter = 0 
    # assign a color to the first node being visited 
    colors[1] = 0 

    while open_list: 
     # up the counter here so that all neighbors get the same color 
     color_counter += 1 
     # use first elem for bfs 
     current_neighbors = G[open_list[0]] 
     current_color = color_counter % 2 
     # prints used for debugging 
     print open_list 
     print "The current color is: %s" % (current_color,) 
     for neighbor in current_neighbors: 
      if neighbor not in colors: 
       open_list.append(neighbor) 
       colors[neighbor] = current_color 
       # print used for debugging 
       print "parent is: %s, child is: %s, %s's color is: %s" \ 
       % (open_list[0], neighbor, neighbor, colors[neighbor]) 
       # print used for debugging 
      else: print "parent is: %s, child is: %s, already colored: %s" \ 
       % (open_list[0], neighbor, colors[neighbor]) 
     open_list.pop(0) 
    # now, return array of values that has one of the two colors 
    zeros_array = [] 
    ones_array = [] 
    for key in colors.keys(): 
     if colors[key] == 0: 
      zeros_array.append(key) 
     else: 
      ones_array.append(key) 

    if len(set(zeros_array) & set(ones_array)) == 0: 
     return zeros_array 
    else: 
     return None 

下面是我使用的图形:

{1: {2: 1, 4: 1}, 2: {1: 1, 3: 1, 5: 1}, 3: {8: 1, 2: 1}, 4: {1: 1}, 5: {2: 1, 6: 1}, 6: {5: 1}, 8: {3: 1}} 

我画出来,图形可以看作以1为根的树,并分支到节点2和4,其中4是叶子,但是2继续前进。我使用颜色计数器为相邻颜色着色相同的颜色(0或1)。 2和4被赋予相同的颜色,那么算法正确地给出了父亲2的相反颜色的3和5,但是当返回一个等级到4时,颜色计数器增加,所以当它达到8时, 8得到错误的颜色。

我被困在如何最好地解决这个问题。

回答

0

你应该选择的颜色取决于当前的顶点颜色,像colors[neighbor] = (colors[open_list[0]] + 1) % 2

此外,len(set(zeros_array) & set(ones_array)) == 0永远是true,这样你就不会检查是偶进展顺利。您可以在if neighbor not in colors:的其他分支中检查它:只声明您的邻居与当前顶点具有不同的颜色。

+0

将你的行修改为:colors [neighbor] =(colors [open_list [0]] + 1)%2并且工作。在没有你的情况下不能到达那里,谢谢! –

+0

是的,我拼错了 – mingaleg