在航班图这类有向图结构中，每个节点代表城市，边代表两个城市之间的直飞航班。要找出从起点到终点的所有路径，核心思路是沿着当前节点的邻接节点不断向下探索，当到达终点时记录当前路径，当没有可探索的邻接节点时返回上层递归，利用递归调用栈自动维护路径状态，不需要额外传入路径存储参数。
核心实现逻辑
递归函数的设计需要遵循两个核心原则：一是每次递归调用时，当前探索的节点就是新的起点，二是递归返回时不需要手动清理路径状态，因为递归栈的弹出会自动回到上一层的节点状态。具体步骤如下：
- 定义递归函数，接收当前节点、终点、航班图三个参数，不需要额外传入路径列表
- 如果当前节点等于终点，说明找到了一条完整路径，直接返回包含当前节点的路径列表
- 如果当前节点没有邻接节点，返回空列表表示没有找到路径
- 遍历当前节点的所有邻接节点，对每个邻接节点递归调用函数，将返回的所有路径前面拼接上当前节点，最终汇总所有路径返回
Python代码实现
以下是基于上述逻辑的具体代码实现，航班图用字典结构表示，键是城市名称，值是该城市可直飞的所有城市列表：
# 定义航班图，键为出发城市，值为可直飞到达的城市列表
flight_graph = {
"北京": ["上海", "广州"],
"上海": ["广州", "深圳"],
"广州": ["深圳", "成都"],
"深圳": ["成都"],
"成都": []
}
def find_all_paths(current, end, graph):
# 递归终止条件：当前节点就是终点，返回包含当前节点的路径
if current == end:
return [[current]]
# 如果当前节点没有邻接节点，返回空列表
if current not in graph or not graph[current]:
return []
all_paths = []
# 遍历当前节点的所有邻接节点
for neighbor in graph[current]:
# 递归查找邻接节点到终点的所有路径
sub_paths = find_all_paths(neighbor, end, graph)
# 将当前节点拼接到每条子路径的前面
for path in sub_paths:
all_paths.append([current] + path)
return all_paths
# 测试：查找北京到成都的所有航班路径
start = "北京"
end = "成都"
result = find_all_paths(start, end, flight_graph)
print(f"从{start}到{end}的所有路径：")
for path in result:
print(" -> ".join(path))
代码逻辑解析
上述代码中，find_all_paths函数没有接收额外的路径参数，完全依靠递归返回的结果拼接路径。当递归到终点成都时，返回[["成都"]]，上一层的深圳节点收到这个结果后，会拼接成["深圳", "成都"]，再返回给广州节点，广州节点会分别处理深圳和成都两个邻接节点的返回结果，最终拼接出所有包含广州的路径，以此类推直到回到起点北京，汇总所有路径。
复杂度与适用场景
该方案的时间复杂度取决于航班图中的路径总数，假设总共有M条从起点到终点的路径，每条路径平均长度为K，那么时间复杂度为O(M*K)。空间复杂度主要来自递归调用栈，最大深度等于最长路径的长度，不需要额外开辟路径存储的空间，适合路径长度适中、不需要额外维护路径状态的场景。
需要注意的是，如果航班图中存在环（比如某个城市可以飞回之前的城市），该递归逻辑会陷入无限循环，因此使用前需要确保航班图是无环有向图，或者额外添加已访问节点的判断逻辑，但添加已访问判断就需要传入额外的参数，不符合无需额外参数的要求，所以本方案仅适用于无环的航班图场景。