使用DFS算法查找两点间路径：我的Python代码输出是否正确？

我编写了如下Python代码实现DFS算法，用于查找邻接矩阵中两点间的路径：

def DFS(matrix, start, end):
    # TODO:

    path = []
    visited = {}

    stack = []  
   
    stack.append([start])
  
    visited.update({start: None})

    while stack:

        path = stack.pop()  
        node = path[-1] 

        if node == end:  
            break
        for i in range(len(matrix[node])):
            if matrix[node][i] > 0 and i not in visited:
                new_path = list(path)  
                new_path.append(i)  
                stack.append(new_path)  
                visited.update({i: node})
    print(path)
    return visited, path

输入为邻接矩阵，首行是起点和终点节点：

1 6
0 0 9 3 0 0 9 0
0 0 8 5 5 7 6 7
6 9 0 4 2 5 6 8
5 1 2 0 2 4 7 9
0 3 6 8 0 6 6 5
0 6 3 9 9 0 4 0
5 1 8 1 5 3 0 5
0 3 9 8 3 0 7 0

我的代码输出路径为[1,6]，请问该结果是否符合DFS算法的规则？

这个输出完全符合DFS算法的规则，原因如下：

• 先看输入的邻接矩阵：起点是1，对应矩阵的第二行（索引1），该行中索引6的位置值为6>0，说明节点1和节点6直接连通。
• 你的DFS执行流程是：
  1. 初始化栈，把起点路径[1]压入栈，标记起点已访问。
  2. 弹出栈顶的[1]，取末尾节点1。
  3. 遍历节点1的邻接节点，发现节点6未被访问且有连通边，于是生成新路径[1,6]压入栈，同时标记6已访问。
  4. 下一次循环弹出栈顶的[1,6]，发现末尾节点6就是终点，直接终止循环并输出这条路径。

DFS的核心是深度优先探索，但它并不强制要求必须走最长路径——只要在探索过程中找到终点，就可以终止（你的代码逻辑正是如此）。所以这次直接找到起点到终点的直连路径，完全符合DFS的执行规则。

内容的提问来源于stack exchange，提问作者LaFraise