Find the nearest clone

  • + 0 comments

    Javascript BFS

    function findShortest(graphNodes, graphFrom, graphTo, ids, val) {
      let heads = []
      for (let i = 1; i <= graphNodes; i++) if (ids[i - 1] == val) heads.push(i)
    
      for (let head of heads) {
        let queue = [head], levelCount = 0, visited = new Array(ids.length).fill(false)
        visited[head] = true
        while (queue.length > 0) {
          let levelSize = queue.length
          while (levelSize--) {
            let curr = queue.shift()
            if (!visited[curr] && ids[curr - 1] == val) return levelCount
            visited[curr] = true
            for (let i = 1; i <= graphFrom.length; i++) {
              if (graphFrom[i - 1] == curr && !visited[graphTo[i - 1]])
                queue.push(graphTo[i - 1])
              if (graphTo[i - 1] == curr && !visited[graphFrom[i - 1]])
                queue.push(graphFrom[i - 1])
            }
          }
          levelCount++
        }
      }
      return -1
    }