Lekcja – Wykrywanie cykli w grafie
graph = [
[1, 4],
[2,3,4],
[3],
[],
[4,5],
[]
]
def has_cycle_to_node(graph, node, visited, path):
visited[node] = True
path.append(node)
for neighbour in graph[node]:
if not visited[neighbour]:
if has_cycle_to_node(graph, neighbour, visited, path):
return True
if neighbour in path:
cycle = path.copy()
while cycle[0] != neighbour:
del cycle[0]
cycle.append(neighbour)
print(cycle)
return True
del path[-1]
return False
def has_cycle(graph):
visited = [False] * len(graph)
path = []
for node in range(len(graph)):
if not visited[node]:
if has_cycle_to_node(graph, node, visited, path):
return True
return False
if has_cycle(graph):
print("Graph has a cycle")
else:
print("Graph has no cycle")
Lab
names = ['Dad', 'Mum', 'Grandma', 'Grandpa','Doughter', 'Son']
history = [
[0,1,0,0,0,0],
[0,0,1,0,0,0],
[0,0,0,0,1,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0],
[0,0,0,0,0,0]
]
def has_cycle_to_node(graph, node, visited, path):
visited[node] = True
path.append(node)
neighbours = []
for n in range(len(graph[node])):
if graph[node][n] == 1:
neighbours.append(n)
for neighbour in neighbours:
if visited[neighbour] == False:
if has_cycle_to_node(graph, neighbour, visited, path):
return True
if neighbour in path:
cycle = path.copy()
while cycle[0] != neighbour:
del cycle[0]
cycle.append(neighbour)
print([names[i] for i in cycle])
return True
del path[-1]
return False
source=4
for candidate in range(len(names)):
org_value = history[source][candidate]
history[source][candidate] = 1
visited = [False for x in range(len(names))]
path = []
has_cycle = has_cycle_to_node(history, source, visited, path)
history[source][candidate] = org_value
if has_cycle:
print(f'Giving the gift to {names[candidate]} would make a loop')
else:
print(f'OK to give the gift to {names[candidate]}')