Find the nearest clone

  • + 0 comments

    javascript

    function findShortest(graphNodes, graphFrom, graphTo, ids, val) {
      let map = new Map()
      for (let i = 0; i < graphFrom.length; i++) {
        if (!map.has(graphFrom[i])) map.set(graphFrom[i], [])
        map.get(graphFrom[i]).push(graphTo[i])
        if (!map.has(graphTo[i])) map.set(graphTo[i], [])
        map.get(graphTo[i]).push(graphFrom[i])
      }
    
      let nodesToInvestigate = []
      for (let i = 1; i <= ids.length; i++) {
        if (ids[i - 1] == val) nodesToInvestigate.push(i)
      }
    
      if (nodesToInvestigate.length < 2) return -1
    
      let visited = new Set(), distances = []
      for (let i = 0; i < nodesToInvestigate.length; i++) {
        let queue = [[nodesToInvestigate[i], 0]]
        visited.add(nodesToInvestigate[i])
        while (queue.length > 0) {
          let [cur, steps] = queue.shift()
          visited.add(cur)
          if (ids[cur - 1] == val && cur != nodesToInvestigate[i]) {
            distances.push(steps)
            continue
          }
          queue.push(...map.get(cur).filter(to => !visited.has(to))
            .map(node => [node, steps + 1]))
        }
      }
      return Math.min(...distances)
    }