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)```