0
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得到错误的颜色。
我被困在如何最好地解决这个问题。
将你的行修改为:colors [neighbor] =(colors [open_list [0]] + 1)%2并且工作。在没有你的情况下不能到达那里,谢谢! –
是的,我拼错了 – mingaleg