사용 BFS

Question

코드 :

{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}} 

내가 그것을 그린 그래프는 다음과 같이 시각화 할 수 있습니다

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와 노드 4로 분기됩니다. 여기서 4는 리프이지만 2는 계속 진행됩니다. 컬러 카운터를 사용하여 같은 색 (0 또는 1)으로 이웃을 색칠합니다. 2와 4에 같은 색이 주어지면 알고리즘은 3과 5에 부모 2의 반대 색을 올바르게 표시하지만 한 수준을 4로 확인하면 색 카운터가 증가하므로 8에 도달 할 때까지, 8 잘못된 색상을 가져옵니다.

이 문제를 가장 잘 해결하는 방법에 어려움이 있습니다. , len(set(zeros_array) & set(ones_array)) == 0 항상 true 될 것

Answer 1

당신은 당신이 체크되지 않도록 잘 간 양자는, 당신의 현재의 정점 색상에 따라도 colors[neighbor] = (colors[open_list[0]] + 1) % 2

같은 것을 색상을 선택해야합니다. if neighbor not in colors:의 다른 브랜치에서 확인할 수 있습니다. 이웃이 현재 정점과 다른 색을 가지고 있다고 단언하십시오.