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.
42 lines
1013 B
42 lines
1013 B
11 months ago
|
import numpy as np
|
||
|
|
|
||
|
|
inf = float('inf')
|
||
|
|
|
||
|
|
|
||
|
|
def find_all_cycles(distances):
|
||
|
|
num_nodes = distances.shape[0]
|
||
|
|
visited = [False] * num_nodes
|
||
|
|
cycles = []
|
||
|
|
|
||
|
|
def dfs(node, start, path):
|
||
|
|
visited[node] = True
|
||
|
|
for neighbor in range(num_nodes):
|
||
|
|
if distances[node, neighbor] != inf:
|
||
|
|
if neighbor == start and len(path) > 1:
|
||
|
|
cycles.append(path + [start])
|
||
|
|
elif not visited[neighbor]:
|
||
|
|
dfs(neighbor, start, path + [neighbor])
|
||
|
|
visited[node] = False
|
||
|
|
|
||
|
|
for start_node in range(num_nodes):
|
||
|
|
dfs(start_node, start_node, [start_node])
|
||
|
|
|
||
|
|
return cycles
|
||
|
|
|
||
|
|
|
||
|
|
distances = np.array([
|
||
|
|
[inf, inf, 21, inf, 53],
|
||
|
|
[inf, inf, 77, 84, 93],
|
||
|
|
[21, 77, inf, inf, 53],
|
||
|
|
[inf, 84, inf, inf, inf],
|
||
|
|
[53, 93, 53, inf, inf]
|
||
|
|
])
|
||
|
|
|
||
|
|
all_cycles = find_all_cycles(distances)
|
||
|
|
|
||
|
|
if all_cycles:
|
||
|
|
print("存在的回路路径为：")
|
||
|
|
for cycle in all_cycles:
|
||
|
|
print(cycle)
|
||
|
|
else:
|
||
|
|
print("不存在回路")
|