교차로로 자바 스크립트 그룹 배열

Question

쌍으로 구성된 정수의 배열이 주어지면 HOW로 교차로를 그룹화 할 수 있습니다. 누구든지 내 입력을 원하는 출력으로 변환 할 수있는 간단한 함수를 가지고 있습니까?

입력

var in = ["0:3", "1:3", "4:5", "5:6", "6:8"] 

원하는 출력

[ 
    [0, 1, 3], 
    [4, 5, 6, 8] 
] 

UPDATE :

이

"각 숫자를 고려 : 더 명확하게 나는 원래 게시 된 의견에 내 질문을 @apsiller

그래프의 노드로, 각 쌍은 x:y으로 노드 x과 y 사이의 에지는 정의 된 에지를 사용하여 이동할 수있는 숫자 세트를 찾습니다. 즉, 그래프 이론 용어로, 그러한 그래프 내에서 뚜렷한 connected components을 찾으십시오.

예를 들어, 다른 그룹에 있기 때문에 4에서 0으로 이동할 수있는 방법이 없지만 같은 그룹에 속하도록 1에서 0 (3을 기준으로) 이동하는 방법이 있습니다. " 원하는 출력을 유지하기 위해

설정 잠재적으로 임의의 입력에 따라, transversable 노드의 그룹입니다.

Answer 1

감사합니다 여러분. 모든 사람들의 의견을 듣고 나에게 내 대답을 이끌어 낸 비슷한 질문을 찾을 수있었습니다. Finding All Connected Components of an Undirected Graph

첫 번째 단계는 내 입력을 쌍 그룹으로 변경하는 것입니다.

var input = [ 
    [0, 3], 
    [1, 3], 
    [4, 5], 
    [5, 6], 
    [6, 8] 
] 

다음 단계는 ... 모두 함께 퍼팅 폭 우선 검색

function breadthFirstSearch(node, nodes, visited) { 
    var queue = []; 
    var group = []; 
    var pair = null; 
    queue.push(node); 
    while (queue.length > 0) { 
     node = queue.shift(); 
     if (!visited[node]) { 
      visited[node] = true; 
      group.push(node); 
      for (var i = 0, len = nodes.length; i < len; i++) { 
       pair = nodes[i]; 
       if (pair[0] === node && !visited[pair[1]]) { 
        queue.push(pair[1]); 
       } else if (pair[1] === node && !visited[pair[0]]) { 
        queue.push(pair[0]); 
       } 
      } 
     } 
    } 
    return group; 
}; 

---

function groupReachableVertices(input) { 
    var groups = []; 
    var visited = {}; 
    for (var i = 0, len = input.length; i < len; i += 1) { 
     var current_pair = input[i]; 
     var u = current_pair[0]; 
     var v = current_pair[1]; 
     var src = null; 
     if (!visited[u]) { 
      src = u; 
     } else if (!visited[v]) { 
      src = v; 
     } 
     if (src) { 
      groups.push(breadthFirstSearch(src, input, visited)); 
     } 
    } 
    return groups; 
}; 

---

라는 뭐죠 사용하는 것이 었습니다

var output = groupReachableVertices(input); 
[ 
    [0, 1, 3], 
    [4, 5, 6, 8] 
] 

,

Answer 2

당신이 뭔가를 할 수 있습니다.

function group(data) { 
 
    var r = [[]],c = 0,a = [0] 
 
    var d = data.map(e => e.split(':').sort((a, b) => a - b)).sort((a, b) => a[0] - b[0]) 
 
    
 
    d.forEach(function(e, i) { 
 
    if (e[0] > a[a.length - 1]) { 
 
     r.push(e) 
 
     a.push(e[1]) 
 
     c++ 
 
    } else { 
 
     r[c] = r[c].concat(e) 
 
     a[a.length - 1] = e[1] 
 
    } 
 
    }) 
 
    return r.map(e => [...new Set(e)].sort((a, b) => a - b)) 
 
} 
 

 
var test1 = ["0:3", "1:3", "4:5", "5:6", "6:8"] 
 
var test2 = ["0:3", "1:3", "4:5", "9:11", "10:12", '3:6', "7:8"] 
 
var test3 = ["20:15", "4:0", "1:3", "5:1", "9:11", "10:12", '3:6', "8:7"] 
 

 
console.log(JSON.stringify(group(test1))) 
 
console.log(JSON.stringify(group(test2))) 
 
console.log(JSON.stringify(group(test3)))

Answer 3

해시 테이블을 사용하여 해시 테이블의 모든 노드를 수집 할 수 있습니다. 모든 값에 적용됩니다.

var data = ["0:3", "1:3", "4:5", "a:8", "5:a"], 
 
    result = data 
 
     .map(function (a) { return a.split(':'); }) 
 
     .reduce(function (hash) { 
 
      return function (r, a) { 
 
       if (hash[a[0]] && hash[a[1]]) { 
 
        hash[a[0]].push.apply(hash[a[0]], r.splice(r.indexOf(hash[a[1]]), 1)[0]); 
 
        hash[a[1]] = hash[a[0]]; 
 
        return r; 
 
       } 
 
       if (hash[a[0]]) { 
 
        hash[a[1]] = hash[a[0]]; 
 
        hash[a[1]].push(a[1]); 
 
        return r; 
 
       } 
 
       if (hash[a[1]]) { 
 
        hash[a[0]] = hash[a[1]]; 
 
        hash[a[0]].push(a[0]); 
 
        return r; 
 
       } 
 
       hash[a[0]] = a.slice(); 
 
       hash[a[1]] = hash[a[0]]; 
 
       return r.concat([hash[a[0]]]); 
 
      }; 
 
     }(Object.create(null)), []); 
 

 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 4

Object.values() 및 Set 개체를 사용하면 ES6에서 다음과 같이 간단히 수행 할 수 있습니다.

function getConnectedVertices(a){ 
 
    return [...new Set(Object.values(a.reduce((h,v) => (h[v[0]] ? h[v[1]] ? (h[v[0]] = h[v[0]].concat(h[v[1]]), 
 
                      h[v[1]] = h[v[0]]) 
 
                     : (h[v[0]].push(v[1]), 
 
                      h[v[1]] = h[v[0]]) 
 
                   : h[v[1]] ? (h[v[1]].push(v[0]), 
 
                      h[v[0]] = h[v[1]]) 
 
                     : h[v[0]] = h[v[1]] = v, 
 
              h),{})))]; 
 
} 
 

 
var input = ["0:3", "1:3", "4:5", "5:6", "6:8"].map(s => s.split(":")), 
 
    result = getConnectedVertices(input); 
 
console.log(result);