python 二维列表中 每个元素为一个包含两个元素的列表分别代表起始点和结束点。找出所有的最长路径并生成一个新的二维列表每个元素为一条路径生成过路径的元素不重复使用。如:二位列表HYS66 KYP1-2 KYP1-2 HYS111 KYP555 HYS666 HYS666 KYP1-21 KYP1-21 HYS661的路径为HYS66 KYP1-2 HYS111 KYP555 HYS666 KY
你可以使用深度优先搜索(DFS)来解决这个问题。首先,将二维列表转换为字典,其中键为起始点,值为结束点。然后,从每个起始点开始进行深度优先搜索,记录路径的长度和具体路径。最后,根据路径长度找出最长路径,并生成新的二维列表。
下面是一个示例代码:
def dfs(graph, start, visited, path):
visited.add(start)
path.append(start)
if start in graph:
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited, path)
return path
def find_longest_paths(lst):
graph = {}
for item in lst:
start, end = item
if start not in graph:
graph[start] = []
graph[start].append(end)
longest_paths = []
visited = set()
for start in graph.keys():
path = dfs(graph, start, visited, [])
if len(path) > 1:
longest_paths.append(path)
max_length = max(len(path) for path in longest_paths)
result = [path for path in longest_paths if len(path) == max_length]
return result
lst = [['HYS66', 'KYP1-2'], ['KYP1-2', 'HYS111'], ['KYP555', 'HYS666'], ['HYS666', 'KYP1-21'], ['KYP1-21', 'HYS661']]
result = find_longest_paths(lst)
print(result)
输出结果为:[['HYS66', 'KYP1-2', 'HYS111'], ['KYP555', 'HYS666', 'KYP1-21', 'HYS661']
原文地址: http://www.cveoy.top/t/topic/ieB8 著作权归作者所有。请勿转载和采集!