DFS的堆栈实现。除了第一个，所有测试用例都有效

Question

来自https://structy.net/problems/largest-component

编写一个函数，largestComponent，接受一个无向图的邻接表。该函数应 return 图中最大连通分量的大小。

问题是此代码适用于除第一个以外的所有测试用例。我不想用递归 DFS 方法解决这个问题我想使用堆栈或队列 DFS 方法。

主要功能

const largestComponent = (graph) => {
    //init the largest count variable to 0
    let largest=0;
    // use a global set data structure to keep track of visited nodes
    let visited =  new Set();
        
    //loop through graph object and send each node to DFS function
    for (node in graph) {
        //if node has been visited then skip to next node
        if(visited.has(String(node))) continue;
    
        let currentCount = DFS(graph, node, visited);
        
        // get largest count per iteration
        largest = Math.max(largest, currentCount);
    
    }
    // return result
    return largest;
}

深度优先搜索功能

const DFS = (graph, node, visited) => {
        
    // initiate count for neighbors of current node but also count current node so init to 1
    let currentCount = 1;
    
    // populate stack with node
    let stack = [node];
    
    //loop for as long as stack isn't empty
    while(!!stack.length){
   
        // get current node from stack
        let current = stack.pop();
            
        // mark node as visited
        visited.add(String(current));
        
        // loop through neighbors of node
        for( neighbor of graph[current]){

            // if neighbors have been visited already then skip them
            if(visited.has(String(neighbor))){
                continue;
            } else {
                // add neighbor to count
                currentCount++;
                    
                // add the next neighbor to stack
                stack.push(neighbor);
            }
        }
    }
    // return count of connected components for current node
    return currentCount;
}

测试用例 1

console.log(largestComponent({
  0: ['8', '1', '5'],
  1: ['0'],
  5: ['0', '8'],
  8: ['0', '5'],
  2: ['3', '4'],
  3: ['2', '4'],
  4: ['3', '2']
})) // should give -> 4

测试用例 2

console.log(largestComponent({
  1: ['2'],
  2: ['1','8'],
  6: ['7'],
  9: ['8'],
  7: ['6', '8'],
  8: ['9', '7', '2']
})); // should give  -> 6

测试用例 3

console.log(largestComponent({
  3: [],
  4: ['6'],
  6: ['4', '5', '7', '8'],
  8: ['6'],
  7: ['6'],
  5: ['6'],
  1: ['2'],
  2: ['1']
})); // should give -> 5

测试用例 4

console.log(largestComponent({
  0: ['4','7'],
  1: [],
  2: [],
  3: ['6'],
  4: ['0'],
  6: ['3'],
  7: ['0'],
  8: []
})); // should give -> 3

Answer 1

原因

在测试用例 1 中发生的情况是您对 8 计数两次（电流为 0 时一次，电流为 5 时一次）。

一步一步：

1. 当前节点为0，currentCount=1，stack=[]，visited=[]
   • 将 0 标记为已访问 -> [0]
   • 添加到堆栈：8、1、5 -> [8, 1, 5]
   • 当前计数变为：1 + 3
2. 当前节点为5，currentCount=4，stack=[8, 1]（弹出5），visited=[0]
   • 将 5 标记为已访问 -> [0, 5]
   • 添加到堆栈：8（访问了 0 个，但仍然没有访问 8 个）-> [8, 1, 8]
   • 当前计数变为：4 + 1 问题出在这里

解决方案

这可以通过改变三件事来解决：

1. 访问时计算节点数（而不是检查邻居时）。
2. 作为第 1 点的结果，currentCount 变量从 0 开始。
3. 检查从堆栈弹出的 current 节点是否未被访问。

代码

最终代码会是这样的：

const largestComponent = (graph) => {
    //init the largest count variable to 0
    let largest=0;
    // use a global set data structure to keep track of visited nodes
    let visited =  new Set();
        
    //loop through graph object and send each node to DFS function
    for (node in graph) {
        //if node has been visited then skip to next node
        if(visited.has(String(node))) continue;
    
        let currentCount = DFS(graph, node, visited);
        
        // get largest count per iteration
        largest = Math.max(largest, currentCount);
    
    }
    // return result
    return largest;
}

const DFS = (graph, node, visited) => {

    // count starts at 0, `node` will always be counted in the first iteration
    let currentCount = 0;
    
    // populate stack with node
    let stack = [node];
    
    //loop for as long as stack isn't empty
    while(!!stack.length) {
   
        // get current node from stack
        let current = stack.pop();

        // if current node has been visited then skip to next node
        if (visited.has(String(current))) continue;
        
        // mark node as visited and count it
        visited.add(String(current));
        currentCount++;
        
        // loop through neighbors of node
        for( neighbor of graph[current]){

            // if neighbors have been visited already then skip them
            if(visited.has(String(neighbor))){
                continue;
            } else {
                // add the next neighbor to stack
                stack.push(neighbor);
            }
        }
    }
    // return count of connected components for current node
    return currentCount;
}