基于递归DFS算法判断图中两节点间是否存在路径的实现问题

先把你提供的代码片段整理出来：

public static bool RouteBetweenNodes_DFS(Node a, Node b) { 
    if (a == null || b == null) return false; 
    // 若尚未返回'true'，则标记当前节点为已访问并遍历其子节点 
    a.visited = true; 
    Console.WriteLine("A: " + a.data + ", B: " + b.data); 
    // 我们将此作为递归时的判断条件……
}

这段代码目前缺少核心的递归判断逻辑，我来帮你补全并梳理关键细节：

第一步：明确Node类的基础定义 #

首先需要一个标准的Node类来支撑图结构：

public class Node {
    public string data; // 节点存储的数据，可替换为int等其他类型
    public List<Node> neighbors; // 存储当前节点的所有邻接节点（有向边指向的节点）
    public bool visited; // 标记节点是否被访问过，避免循环遍历

    public Node(string data) {
        this.data = data;
        neighbors = new List<Node>();
        visited = false; // 初始化时默认未访问
    }
}

第二步：完整的递归DFS实现 #

public static bool RouteBetweenNodes_DFS(Node a, Node b) {
    // 边界校验：任意节点为空，直接返回无路径
    if (a == null || b == null) return false;
    
    // 终止条件：当前节点就是目标节点，说明找到路径
    if (a == b) return true;
    
    // 标记当前节点为已访问，防止重复遍历导致死循环
    a.visited = true;
    Console.WriteLine($"正在访问节点: {a.data}，目标节点: {b.data}");
    
    // 递归遍历当前节点的所有邻接节点
    foreach (Node neighbor in a.neighbors) {
        // 只遍历未访问过的节点
        if (!neighbor.visited) {
            // 如果邻接节点的递归调用返回true，说明找到路径，立即返回
            if (RouteBetweenNodes_DFS(neighbor, b)) {
                return true;
            }
        }
    }
    
    // 所有邻接节点都遍历完毕仍未找到目标节点，返回无路径
    return false;
}

关键注意事项 #

• 访问标记的重置：如果这个方法需要被多次调用（比如多次查询不同节点对），每次查询前必须重置所有节点的visited状态，否则之前的访问记录会干扰后续查询。可以添加一个辅助方法来完成重置：

public static void ResetAllVisited(Node startNode) {
    if (startNode == null || !startNode.visited) return;
    startNode.visited = false;
    // 递归重置所有邻接节点的访问状态
    foreach (Node neighbor in startNode.neighbors) {
        ResetAllVisited(neighbor);
    }
}

调用示例：

// 假设graphRoot是图的根节点（或任意能遍历到所有节点的起始点）
ResetAllVisited(graphRoot);
bool hasPath = RouteBetweenNodes_DFS(nodeA, nodeB);

• 递归深度限制：如果你的图是深度极大的链式结构，递归DFS可能会触发栈溢出错误。这种情况下，建议改用迭代式DFS（用栈模拟递归过程）来避免这个问题：

public static bool RouteBetweenNodes_IterativeDFS(Node a, Node b) {
    if (a == null || b == null) return false;
    if (a == b) return true;

    Stack<Node> stack = new Stack<Node>();
    stack.Push(a);
    a.visited = true;

    while (stack.Count > 0) {
        Node current = stack.Pop();
        Console.WriteLine($"正在访问节点: {current.data}，目标节点: {b.data}");
        
        foreach (Node neighbor in current.neighbors) {
            if (neighbor == b) return true;
            if (!neighbor.visited) {
                neighbor.visited = true;
                stack.Push(neighbor);
            }
        }
    }
    return false;
}

• 有向图与无向图适配：上述代码对有向图完全适用；如果是无向图，只需要在添加边的时候同时把对方加入彼此的邻接列表即可，访问标记的逻辑不需要改动。

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