You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
46 lines
1.2 KiB
46 lines
1.2 KiB
11 months ago
|
import numpy as np
|
||
|
|
|
||
|
|
inf = float('inf')
|
||
|
|
|
||
|
|
distances = np.array([
|
||
|
|
[inf, 72, inf, inf, 81, 67],
|
||
|
|
[72, inf, 26, inf, 61, inf],
|
||
|
|
[inf, 26, inf, 53, 97, inf],
|
||
|
|
[inf, inf, 53, inf, inf, inf],
|
||
|
|
[81, 61, 97, inf, inf, 38],
|
||
|
|
[67, inf, inf, inf, 38, inf]
|
||
|
|
])
|
||
|
|
|
||
|
|
def find_cycles(start, distances):
|
||
|
|
n = len(distances)
|
||
|
|
path = [start]
|
||
|
|
cycles = []
|
||
|
|
|
||
|
|
def is_valid(node, position):
|
||
|
|
if distances[path[position - 1]][node] == inf:
|
||
|
|
return False
|
||
|
|
if node in path:
|
||
|
|
return False
|
||
|
|
return True
|
||
|
|
|
||
|
|
def find_paths(node):
|
||
|
|
for next_node in range(n):
|
||
|
|
if is_valid(next_node, len(path)):
|
||
|
|
path.append(next_node)
|
||
|
|
if len(path) < n:
|
||
|
|
find_paths(next_node)
|
||
|
|
elif len(path) == n and distances[path[-1]][start] != inf:
|
||
|
|
cycles.append(path.copy())
|
||
|
|
path.pop()
|
||
|
|
|
||
|
|
find_paths(start)
|
||
|
|
return cycles
|
||
|
|
|
||
|
|
all_cycles = find_cycles(0, distances)
|
||
|
|
|
||
|
|
if all_cycles:
|
||
|
|
print("经过全部节点能返回起点的回路的全部路径为：")
|
||
|
|
for cycle in all_cycles:
|
||
|
|
print(cycle + [cycle[0]]) # 添加起点以形成完整的回路
|
||
|
|
else:
|
||
|
|
print("不存在经过全部节点能返回起点的回路")
|