import copy
def question25(neighbor_matrix):
cycle = []
for i in range(len(neighbor_matrix)):
queue = []
for j in range(len(neighbor_matrix)):
if neighbor_matrix[i][j] == 1:
queue.append([i, j])
while len(queue) > 0:
path = queue.pop()
for j in range(len(neighbor_matrix)):
if neighbor_matrix[path[-1]][j] == 1:
path_new = copy.deepcopy(path)
if j in path_new:
#print(j, " in ", path_new)
if j == path_new[0] and len(path_new) > 2:
#print("cycle=", path_new)
if len(cycle) < len(path_new):
cycle = path_new
else:
path_new.append(j)
queue.append(path_new)
#print(path, path_new, queue)
return cycle
n = 5
G = \
[[0, 0, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0]]
question25(G)
[1, 4, 3]
n = 8
G = \
[[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]]
question25(G)
[]
n = 10
G = \
[[0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
[0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 0, 1, 0, 0, 0]]
question25(G)
[0, 9, 3, 7, 8, 1]