CODEWITHSUNDEEP
javascriptjavaalgorithmgraphdepth-first-search
mistervaibhav
mistervaibhav

Reputation: 63

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

I am trying to solve a DFS problem in javascript, the problem is to determine whether the given graph has a path between the given source and destination.

Here is the solution in 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;
    }
}

And here is the JavaScript solution

'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
       
}

The function haspath is the point of interest here, the java solution passes all the test cases, the javascript solution however fails in one test case that is :

7
7
0 1 10
1 2 10
2 3 10
0 3 10
4 5 10
5 6 10
4 6 10
0
6

The function is required to return a boolean value, for the above-mentioned test case, the java solution returns false whereas the js solution returns true

I am not able to figure out what am I doing wrong in JavaScript, Any help is appreciated.

Upvotes: 1

Views: 79

Answers (1)

Aurast
Aurast

Reputation: 3678

There is a subtle bug on this line:

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

This creates only two arrays. new Array(vertices) creates the first new array, and then .fill([]) creates the second and fills the first with references to the second.

So every array in graph is actually the same array. Try running this code to see: 

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";

You can do this to fix that:

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

There may be other problems as well but that's what jumped out at me.

Upvotes: 2

Related Questions