python 任意俩点满足步长要求的所有路径，求指导

如字典表示该节点与其他节点的连通关系，
dct=｛
'A':['B','C','D','E'],
'B':['C','F','H'],
'C':['F'],
'D',['H','I'],
'E',['K']，
'K',['F']
｝
如何运用深度遍历算法，输入始发点，目的点，最大步长，得出俩点间的所有路径？
例：输入始发点A，目的点F，步长4，得出路径A-B-F、A-C-F、A-E-K-F
输入始发点A，目的点F，步长3，得出路径A-B-F、A-C-F
输入始发点A，目的点C，步长任意，得出路径A-C

# 定义函数find_path，它接受四个参数：起点、终点、步长、字典
def find_path(start, end, max_steps, dct):
  # 定义变量paths，用来存储所有满足要求的路径
  paths = []

  # 定义函数dfs，它接受三个参数：当前节点、当前步数、当前路径
  def dfs(node, steps, path):
    # 如果当前步数已经超过最大步长，直接返回
    if steps > max_steps:
      return

    # 如果当前节点已经是终点，把当前路径添加到

所有满足要求的路径中
if node == end:
paths.append(path)
return

# 遍历当前节点的所有相邻节点
for next_node in dct[node]:
  # 如果下一个节点已经在当前路径中出现过，跳过它
  if next_node in path:
    continue

  # 如果没有出现过，继续搜索下一个节点
  dfs(next_node, steps + 1, path + [next_node])
开始搜索
dfs(start, 0, [start])

返回所有满足要求的路径
return paths

测试函数
dct = {
'A': ['B', 'C', 'D', 'E'],
'B': ['C', 'F', 'H'],
'C': ['F'],
'D': ['H', 'I'],
'E': ['K'],
'K': ['F']
}

print(find_path('A', 'F', 4, dct)) # 输出 [['A', 'B', 'F'], ['A', 'C', 'F'], ['A', 'E', 'K', 'F']]
print(find_path('A', 'F', 3, dct)) # 输出 [['A', 'B', 'F'], ['A', 'C', 'F']]
print(find_path('A', 'C', 100, dct)) # 输出 [['A', 'C']]

上面的代码实现了一个深度优先搜索算法，它可以用来搜索从起点到终点的路径，并根据给定的最大步长筛选符合要求的路径。希望这些内容能够帮助到你。

下面是一个完整的代码实现和注释讲解，望采纳

# 定义字典，表示该节点与其他节点的连通关系
dct = {
    'A': ['B', 'C', 'D', 'E'],
    'B': ['C', 'F', 'H'],
    'C': ['F'],
    'D': ['H', 'I'],
    'E': ['K'],
    'K': ['F']
}

# 定义函数，用于深度遍历
def dfs(graph, start, end, step, path):
    # 如果已经遍历到目的节点，则将路径输出
    if start == end:
        print(path)
        return

    # 如果还没有遍历到目的节点，则继续遍历
    if step > 0:
        # 获取当前节点的所有连通节点
        for node in graph[start]:
            # 遍历连通节点，并更新路径
            dfs(graph, node, end, step - 1, path + [node])

# 输入始发点、目的点、步长
start = input('请输入始发点：')
end = input('请输入目的点：')
step = int(input('请输入步长：'))

# 调用函数，进行深度遍历
dfs(dct, start, end, step, [start])

求两点间的所有路径算法
如有帮助，望采纳

"""defgraph.py"""

'''
class Vertex(object):
    def __init__(self,name):
        self.name = name
        self.adjs = []
        self.adjsname = []
        self.isdestn = 0
    
    def look_adjs(self):
        L = []
        for v in self.adjs:
            L.append(v.name)
        print(L)

class Edge(object):
    def __init__(self,v,u):
        self.relevances = {v.name:v.adjs, u.name:u.adjs}

    def look_relevances(self):
        L = []
        for vname in self.relevances.keys():
            L.append(vname)
        print(L)

'''
class Graph(object):
    '''undirected unweighted graph'''

    def __init__(self):
        self.VertexNumber = int(0)
        self.EdgeNumber = int(0)
        self.VertexSet = {}
        self.EdgeSet = []
        self.origin = None
        self.destn = None
        self.O2DPathNum = int(0)
    
    def insert_vertex(self,vertex):
        self.VertexSet.setdefault(vertex,[])

    def insert_edge(self,v,u):
        edge = set([v, u])
        if not (edge in self.EdgeSet):
            self.EdgeSet.append(edge)

        '''establish adjacency relationship'''
        if not (u in self.VertexSet[v]):
            self.VertexSet[v].append(u)
        if not (v in self.VertexSet[u]):
            self.VertexSet[u].append(v)

    def get_adjs(self,vertex):
        if vertex in self.VertexSet.keys():
            return self.VertexSet[vertex]
        else:
            print('{} is not in VertexSet'.format(vertex))  

    def look_VertexSet(self):
        L = []
        for v in self.VertexSet.keys():
            L.append(v)    
        print(L)
    
    def look_EdgeSet(self):
        print(self.EdgeSet)

'''All paths of two vertexs.py'''

import string
from defgraph import *

def initialize_graph(G):
    with open('test-5.txt','r') as f:
        G.EdgeNumber = int(f.readline().strip())
        G.VertexNumber = int(f.readline().strip())
        
        '''
        create the EdgeSet and the VertexSet
        notes:enumerate can get the loop count'
        '''
        for i,line in enumerate(f.readlines()):
            if  i == G.EdgeNumber:
                G.origin = line.strip()
            elif i == G.EdgeNumber + 1:
                G.destn = line.strip()
            else:
                u,v = line.strip().split()
            
                G.insert_vertex(v)
                G.insert_vertex(u)

                G.insert_edge(v,u)


def search_path():
    global path
    path = []
    path.append(G.origin)
    visit(G.origin)
    print("Path Number:{}".format(G.O2DPathNum))

def visit(vertex):
    v_adjs = G.get_adjs(vertex) 

    '''whether vertex has adjacences'''
    if v_adjs:
        for u in v_adjs:
            if u == G.destn:
                print(''.join([v for v in path]) + u) 
                G.O2DPathNum += 1
            elif not (u in path):
                path.append(u)
                visit(u)
        '''loop end means that node 'u' has been explored'''
        path.pop()


def main():
    global G
    G = Graph()
    initialize_graph(G)
    '''
    G.look_VertexSet()
    G.look_EdgeSet()
    print(G.get_adjs('A')) 
    '''
    search_path()
    

if __name__ == "__main__":
    main()

解决代码如下:

from itertools import groupby


def findAllPath(graph, start, end, path=[]):
    # path.append(start)
    path = path + [start]
    if start == end:
        return path

    for node in graph[start]:
        if node not in path:
            newpaths = findAllPath(graph, node, end, path)
            for newpath in newpaths:
                if newpath == end:
                    path.append(newpath)
                    paths.append(path)
    return paths


def get_graph(graph_dict):
    # 打散, 获取相关的两个点
    t = [(kvs[0], v) for kvs in graph_dict.items() for vs in kvs[1] for v in vs]
    # 反转两个点, 获取2个点的相互关系
    t_re = [(t2[1], t2[0]) for t2 in t]
    t.extend(t_re)

    # 聚合得到每个点的下个点
    t_g = groupby(sorted(t, key=lambda x: x[0]), key=lambda x: x[0])
    # 每个点的所有直接连接点
    t_dict = {k: [v[1] for v in list(vs)] for k, vs in t_g}
    return t_dict


if __name__ == '__main__':
    graph = {
        'A': ['B', 'C', 'D', 'E'],
        'B': ['C', 'F', 'H'],
        'C': ['F'],
        'D': ['H', 'I'],
        'E': ['K'],
        'K': ['F']
    }
    t_dict = get_graph(graph)

    start, end, step = 'A', 'F', 4
    paths = []  # 存储所有路径
    findAllPath(t_dict, start, end)
    # print(paths)
    # 步长过滤
    paths_result = ['-'.join(p) for p in paths if len(p) <= step]
    print(f'start: {start}, end: {end}, step: {step}, result: {paths_result}')

    start, end, step = 'A', 'F', 3
    paths = []  # 存储所有路径
    findAllPath(t_dict, start, end)
    paths_result = ['-'.join(p) for p in paths if len(p) <= step]
    print(f'start: {start}, end: {end}, step: {step}, result: {paths_result}')

    start, end, step = 'A', 'C', None
    paths = []  # 存储所有路径
    findAllPath(t_dict, start, end)
    paths_result = ['-'.join(p) for p in paths]
    print(f'start: {start}, end: {end}, step: {step}, result: {paths_result}')

打印结果:

start: A, end: F, step: 4, result: ['A-B-C-F', 'A-B-F', 'A-C-F', 'A-E-K-F']
start: A, end: F, step: 3, result: ['A-B-F', 'A-C-F']
start: A, end: C, step: None, result: ['A-B-C', 'A-C']

Process finished with exit code 0