求JavaScript非递归DFS实现：匹配多组含dataMap的对象数组值

Got it, let's break down how to implement a non-recursive Depth-First Search (DFS) for your specific data structure. First, let's confirm the setup: you're working with an array of objects, where each object has two properties:

• dataMap: An array of nested objects with the same structure (this forms your tree/graph of nodes)
• i: A numeric identifier for the node

The core idea behind non-recursive DFS is to use a stack to simulate the call stack that recursive DFS relies on. Let's cover different common traversal types with practical code examples.

1. Pre-Order DFS (Visit Node First, Then Children) #

This is the most straightforward variant—we process the current node immediately, then handle all its nested dataMap nodes.

function nonRecursivePreOrderDFS(rootArray) {
    // Initialize stack with all root-level nodes
    const stack = [...rootArray];

    while (stack.length > 0) {
        // Pop the top node from the stack (LIFO behavior)
        const currentNode = stack.pop();

        // --------------------------
        // Your "visit" logic here
        // --------------------------
        console.log(`Visited node (pre-order) with i: ${currentNode.i}`);
        // Example: collect node data, run transformations, etc.

        // Push children from `dataMap` in reverse order
        // This ensures we process them in the original array order (since stack is LIFO)
        for (let i = currentNode.dataMap.length - 1; i >= 0; i--) {
            stack.push(currentNode.dataMap[i]);
        }
    }
}

How It Works: #

• We start by pushing all root nodes onto the stack.
• For each node we pop, we immediately process (visit) it.
• We then push its dataMap children onto the stack in reverse order—this way, when we pop them next, they're processed in the original order of the dataMap array.

2. Post-Order DFS (Visit Children First, Then Node) #

If you need to process all child nodes before the parent, we use a "marked" stack approach—each stack entry tracks whether we've visited the node's children yet.

function nonRecursivePostOrderDFS(rootArray) {
    // Initialize stack with root nodes marked as unvisited
    const stack = rootArray.map(node => ({ node, visited: false }));

    while (stack.length > 0) {
        const { node, visited } = stack.pop();

        if (visited) {
            // --------------------------
            // Process node AFTER children
            // --------------------------
            console.log(`Processed node (post-order) with i: ${node.i}`);
        } else {
            // Push the node back marked as visited
            stack.push({ node, visited: true });
            // Push children in reverse order to process them left-to-right
            for (let i = node.dataMap.length - 1; i >= 0; i--) {
                stack.push({ node: node.dataMap[i], visited: false });
            }
        }
    }
}

How It Works: #

• The first time we pop a node, we mark it as visited and push it back to the stack.
• We then push all its children onto the stack (unmarked). This ensures the children get processed before the parent node is handled in its second pop.

3. Handling Cycle References (Avoid Infinite Loops) #

If your dataMap structure can have cycles (e.g., Node A's dataMap includes Node B, and Node B's dataMap includes Node A), add a Set to track visited nodes and skip duplicates:

function nonRecursiveDFSWithCycleCheck(rootArray) {
    const stack = [...rootArray];
    const visitedNodes = new Set();

    while (stack.length > 0) {
        const currentNode = stack.pop();

        // Skip if we've already processed this node
        if (visitedNodes.has(currentNode)) continue;
        visitedNodes.add(currentNode);

        console.log(`Visited node (cycle-safe) with i: ${currentNode.i}`);

        for (let i = currentNode.dataMap.length - 1; i >= 0; i--) {
            stack.push(currentNode.dataMap[i]);
        }
    }
}

Key Notes: #

• The stack approach works for any depth of nesting, since we're not limited by call stack size (unlike recursive DFS, which can hit stack overflow for very deep structures).
• Adjust the "visit/process" logic to fit your specific use case (e.g., collecting data into an array, modifying node properties, etc.).

内容的提问来源于stack exchange，提问作者Michael B.