TypeScript中while循环内return未生效的DFS函数问题

我用TypeScript写了一个深度优先搜索（DFS）函数，能正常遍历所有连通节点，但在while循环里的forEach回调中，当当前节点ID和目标ID匹配时，return true没让函数按预期返回——条件确实触发了（控制台打印了'Condition met'），但函数最终还是返回false。这是TypeScript的特性吗？怎么让函数满足条件时立刻终止while循环并返回true？

相关代码 #

function dfs(graph: any, node: any,nodedata: any,target?: any){
    var stack: any[] = []
    var visited: any[] = []
    var visiting = null

    stack.push(node)
    visited.push(node)

    while(stack.length > 0){
        visiting = stack.pop()
        var connectedNodes = graph.getConnectedNodes(visiting.id,"to")
        connectedNodes.forEach(function(itm: any){
            var check_node = nodedata.get(itm)
                console.log("check_node",check_node.id,"target",target.id)

                // 问题出在这里：条件触发但return true没有生效
                if(check_node.id == target.id){
                    console.log('Condition met')
                    return true
                }
                // ----------------------------------------------------------------------

            if(!visited.includes(check_node)){
                visited.push(check_node)
                stack.push(check_node)
            }
        })
    }
    
return false
}

测试代码 #

var checkdfs = dfs(network,nodes.get(1),nodes,nodes.get(4))
if(checkdfs){
   console.log('It returned true')
}else{
   console.log('It returned false')
}

控制台输出 #

check_node 2 target 4
check_node 5 target 4
check_node 3 target 4
check_node 4 target 4
Condition met
It returned false

原因分析 #

这不是TypeScript的特性，而是JavaScript/TypeScript中回调函数的作用域特性：

• forEach的回调是独立函数，你在回调里写的return true只会终止当前回调的执行，既不会跳出外层的forEach循环，也不会让外层的dfs函数返回。
• 外层while循环会继续执行直到栈为空，最后走到函数末尾返回false。

解决方案 #

放弃使用forEach遍历连通节点，改用普通for循环或for...of循环，这样就能在匹配到目标时直接跳出循环并让函数返回true：

修改后的代码 #

function dfs(graph: any, node: any, nodedata: any, target?: any) {
    const stack: any[] = [];
    const visited: any[] = [];
    let visiting = null;

    stack.push(node);
    visited.push(node);

    while (stack.length > 0) {
        visiting = stack.pop();
        const connectedNodes = graph.getConnectedNodes(visiting.id, "to");
        
        // 改用for...of循环遍历
        for (const itm of connectedNodes) {
            const check_node = nodedata.get(itm);
            console.log("check_node", check_node.id, "target", target.id);

            if (check_node.id === target.id) {
                console.log('Condition met');
                return true; // 此处return直接终止dfs函数并返回true
            }

            if (!visited.includes(check_node)) {
                visited.push(check_node);
                stack.push(check_node);
            }
        }
    }

    return false;
}

补充说明 #

• 普通for循环/for...of循环属于外层dfs函数的作用域，内部的return true会直接作用于外层函数，终止所有流程并返回结果。
• 也可以通过标记变量控制（在回调中设置标记，外层判断标记后跳出循环），但用for循环是更直接高效的实现方式。

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