Lekcja – Kolorowanie grafu algorytmem zachłannym
colors = ['yellow','red','green','blue','black'] graph1 = [ [0,1,1,0,0], [1,0,1,1,0], [1,1,0,1,0], [0,1,1,0,1], [0,0,0,1,0] ] graph2 = [ [0,1,1,0,0], [1,0,1,0,1], [1,1,0,0,1], [0,0,0,0,1], [0,1,1,1,0] ] def color_graph(graph): color_list = [None] * len(graph) color_list[0] = 0 for v in range(1, len(graph)): used = [False] * len(graph) neighbours = [x for x in range(len(graph)) if graph[v][x]==1] for i in neighbours: if color_list[i] != None: used[color_list[i]] = True free_color = 0 while used[free_color]: free_color += 1 color_list[v] = free_color return color_list colors_for_graph1 = color_graph(graph1) print([colors[i] for i in colors_for_graph1]) colors_for_graph2 = color_graph(graph2) print([colors[i] for i in colors_for_graph2])
Lab
trips = {
'A' : ['B','C'],
'B' : ['A','C', 'D','E','F'],
'C' : ['A','B'],
'D' : ['B','E','F'],
'E' : ['F','G','H','B','D'],
'F' : ['E','F','D','B'],
'G' : ['E','H','I'],
'H' : ['E','G'],
'I' : ['G']
}
# AAAAA...................
# BBBBBBBBBBBBBB..........
# .CCCC...................
# .....DDDDDDDDD..........
# ...........EEEEEE.......
# ...........FFF..........
# ..............GGGGGGGG..
# ..............HHH.......
# .................IIIIIII
# 012345678901234567890123
def set_assigment(trips):
assigments = {name: None for name in trips.keys()}
machines = []
for t in trips.keys():
used = [False for x in range(len(machines))]
for i in trips[t]:
if assigments[i] != None:
used[assigments[i]] = True
free_machine = 0
while free_machine < len(used) and used[free_machine]:
free_machine += 1
if free_machine == len(machines):
machines.append(free_machine)
assigments[t] = free_machine
return assigments
assigments = set_assigment(trips)
print(assigments)