import copy
def question29(neighbor_matrix):
queue = []
routes = []
k = len(neighbor_matrix) - 1
for j in range(len(neighbor_matrix)):
if neighbor_matrix[0][j] == 1:
if j == k:
routes.append([0, j])
else:
queue.append([0, 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 not in path_new:
path_new.append(j)
if j == k:
routes.append(path_new)
else:
queue.append(path_new)
#print(path, path_new, queue)
return routes
n = 5
G = \
[[0, 0, 1, 0, 0],
[1, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 0, 1, 0, 0]]
question29(G)
[[0, 2, 3, 4]]
n = 8
G = \
[[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0]]
question29(G)
[[0, 1, 4, 7], [0, 1, 3, 6, 7]]
n = 8
G = \
[[0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 0, 0]]
question29(G)
[[0, 7],
[0, 5, 2, 6, 3, 7],
[0, 5, 2, 3, 7],
[0, 5, 1, 6, 3, 7],
[0, 5, 1, 6, 2, 3, 7]]
n = 8
G = \
[[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 1, 0]]
question29(G)
[]