Java 和 JavaScript 中的逻辑相似，但 DFS 的结果不同

Question

我正在尝试解决 java脚本中的 DFS 问题，问题是确定给定的图形是否具有给定源和目标之间的路径。

这是java

中的解决方案

import java.io.*;
import java.util.*;

public class Main {
   static class Edge {
      int src;
      int nbr;
      int wt;

      Edge(int src, int nbr, int wt){
         this.src = src;
         this.nbr = nbr;
         this.wt = wt;
      }
   }
   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int vtces = Integer.parseInt(br.readLine());
      ArrayList<Edge>[] graph = new ArrayList[vtces];
      for(int i = 0; i < vtces; i++){
         graph[i] = new ArrayList<>();
      }

      int edges = Integer.parseInt(br.readLine());
      for(int i = 0; i < edges; i++){
         String[] parts = br.readLine().split(" ");
         int v1 = Integer.parseInt(parts[0]);
         int v2 = Integer.parseInt(parts[1]);
         int wt = Integer.parseInt(parts[2]);
         graph[v1].add(new Edge(v1, v2, wt));
         graph[v2].add(new Edge(v2, v1, wt));
      }

      int src = Integer.parseInt(br.readLine());
      int dest = Integer.parseInt(br.readLine());

        boolean visited[] = new boolean[vtces];
        boolean ans = hasPath(graph , src, dest,visited);
        System.out.println(ans);

 
    }


    static boolean hasPath( ArrayList<Edge> graph[] ,int src,int dest, boolean[] visited){
        
        if(src == dest){
            return true;
        }
 
        visited[src] = true;

        for(Edge edge : graph[src]){
            
            if( visited[edge.nbr] ){
                continue;
            }
            
            boolean nbrHasPath = hasPath(graph, edge.nbr, dest, visited);
            if(nbrHasPath){
                return true;
            }
        }
        return false;
    }
}

这是 JavaScript 解决方案

'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', (inputStdin) => {
  inputString += inputStdin;
});

process.stdin.on('end', (_) => {
  inputString = inputString
    .trim()
    .split('\n')
    .map((string) => {
      return string.trim();
    });

  main();
});

function readline() {
  return inputString[currentLine++];
}

function readIntArray() {
  return readline()
    .split(' ')
    .map((num) => parseInt(num));
}

function readFloatArray() {
  return readline()
    .split(' ')
    .map((num) => parseFloat(num));
}

/*=====================START CODING HERE=====================*/


class Edge {
    
    constructor(source, neighbour, weight){
        this.source = source 
        this.neighbour = neighbour
        this.weight = weight
    }
    
}

function main() {
  
    
 const vertices = parseInt(readline());
 const edges = parseInt(readline());
  
 const graph = new Array(vertices).fill([])


 for(let i = 0 ; i < edges; i++){
    let [s, d, w] = readIntArray()
 
    graph[s].push(new Edge(s,d,w))
    graph[d].push(new Edge(d,s,w))
 }
 
 const source = parseInt(readline());
 const destination = parseInt(readline());
 
 let visited = new Array(vertices).fill(false)

 console.log(hasPath( graph, source, destination,visited ))
 
}

function hasPath(graph, source, dest, visited){
    
 
    if(source === dest){
        return true
    }
    
    visited[source] = true
    
    for(let i = 0; i < graph[source].length; i++){
        
        let edge = graph[source][i]
        
        if( visited[edge.neighbour] ){
            continue;
        }
        
        let nbrHasPath = hasPath(graph, edge.neighbour, dest , visited)
        if(nbrHasPath){
            return true
        }       
    }   
    return false
       
}

函数 haspath 是这里的兴趣点，java 解决方案通过了所有测试用例，但是 javascript 解决方案在一个测试用例中失败了：

函数需要return一个boolean值，对于上述测试用例，java方案returns false而js方案returns true

我无法弄清楚我在 JavaScript 中做错了什么，感谢您的帮助。

Answer 1

这一行有一个细微的错误：

const graph = new Array(vertices).fill([]);

这只创建了两个数组。 new Array(vertices) 创建第一个新数组，然后 .fill([]) 创建第二个并 用对第二个的引用填充第一个 。

所以 graph 中的每个数组实际上都是同一个数组。试试运行这个代码看看：

const graph = new Array(5).fill([]);
graph[0].push('hello');
console.log(graph[0][0]); // prints "hello";
console.log(graph[1][0]); // also prints "hello";
console.log(graph[2][0]); // also prints "hello";
console.log(graph[3][0]); // also prints "hello";
console.log(graph[4][0]); // also prints "hello";

你可以这样做来解决这个问题：

const graph = new Array(vertices).fill().map(() => []);

可能还有其他问题，但这正是我突然想到的。

Java 和 JavaScript 中的逻辑相似，但 DFS 的结果不同

Similar logic in Java and JavaScript, but different results for DFS

javascript

java

algorithm

graph

depth-first-search