Javascript组将键值链接到数组中

首先，我会将关系存储为数组，这样你就可以有重复的"键"。键方法：一个初始字典，包括与每个单词相关的每个单词；使用map和reduce的递归扩链器；基于等价性的过滤链。

Array.prototype.getUnique = function(){
   var u = {}, a = [];
   for(var i = 0, l = this.length; i < l; ++i){
      if(u.hasOwnProperty(this[i])) {
         continue;
      }
      a.push(this[i]);
      u[this[i]] = 1;
   }
   return a;
}
var links = {};
var pairs = [
    ["car", "wheel"],
    ["wheel", "tyre"],
    ["bed", "sheets"],
    ["guitar", "strings"],
    ["guitar", "pickup"],
    ["rubber", "tyre"],
    ["truck", "wheel"],
    ["pickup", "car"]
];
pairs.map(function(pair) {
    links[pair[0]] = links[pair[0]] || [];
    links[pair[1]] = links[pair[1]] || [];
    links[pair[0]].push(pair[1]);
    links[pair[1]].push(pair[0]);
});
var append = function(list) {
    var related = list.map(function(item) {
        return links[item];
    }).reduce(function(listA, listB) {
        return listA.concat(listB);
    }).filter(function(item) {
        // make sure related only includes new links
        return list.indexOf(item) == -1
    }).getUnique();
    return related.length ? append(list.concat(related)) : list.concat(related);
};
var branches = [];
for( var word in links ) {
    branches.push(append(links[word].concat(word)));
}
var compareArrays = function(listA, listB) {
    if( listA.length != listB.length ) return false;
    return listA.map(function(element) {
        if( listB.indexOf(element) == -1 ) return 0;
        return 1;
    }).filter(function(el) {
        return el == 1;
    }).length == listA.length;
};
var _branches = branches;
var chains = branches.filter(function(branch1, i) {     
    var isUnique = _branches.filter(function(branch2) {
        // are they equivalent
        return compareArrays(branch1, branch2);
    }).length == 1; 
    delete _branches[i];
    return isUnique;
});

我会使用单词映射，链接它们当前所在的集合。用于访问键的运行时接近O（1）的映射（javascript对象）应该有助于提高性能。从@matt3141:提出的相同格式开始

var pairs = [
    ["car", "wheel"],
    ["wheel", "tyre"],
    ["bed", "sheets"],
    ["guitar", "strings"],
    ["guitar", "pickup"],
    ["rubber", "tyre"],
    ["truck", "wheel"],
    ["pickup", "car"]
];
var setsByWord = {};
for (var i=0; i<pairs.length; i++) {
    var pair = pairs[i];
    if (pair[0] in setsByWord && pair[1] in setsByWord) {
        // both words are already known
        if (setsByWord[pair[0]] === setsByWord[pair[1]]) {
             ; // We're lucky, they are in the same set
        } else {
             // combine the two sets
             var sets = [setsByWord[pair[0]], setsByWord[pair[1]]];
             var larger = sets[1].length > sets[0].length ? sets[1] : sets[0],
                 smaller = sets[+(larger===sets[0])];
             for (var j=0; j<smaller.length; j++)
                 setsByWord[smaller[j]] = larger;
             Array.prototype.push.apply(larger, smaller);
        }
    } else {
        // add the missing word to the existing set
        // or create a new set
        var set = setsByWord[pair[0]] || setsByWord[pair[1]] || [];
        if (!(pair[0] in setsByWord)) {
            set.push(pair[0]);
            setsByWord[pair[0]] = set;
        }
        if (!(pair[1] in setsByWord)) {
            set.push(pair[1]);
            setsByWord[pair[1]] = set;
        }
    }
}
return setsByWord;

这将在其连接的组件中拆分图形（在setsByWord对象中，这些组件数组由节点索引）：

> var results = [];
> for (var word in setsByWord)
>     if (results.indexOf(setsByWord[word])<0)
>         results.push(setsByWord[word]);
> return results;
[
    ["car","wheel","tyre","rubber","truck","guitar","strings","pickup"],
    ["bed","sheets"]
]

如果你有一个有向图，并且想要所有后续单词的数组，你可以使用这个：

var pairs = […],
    graph = pairs.reduce(function(map, pair) {
         (map[pair[0]] || (map[pair[0]] = [])).push(pair[1]);
         return map;
    }, {});
var successors = {};
for (var word in graph) (function getSuccessors(word) {
    if (word in successors)
        return successors[word];
    successors[word] = [true]; // some marker against circles
    return successors[word] = word in graph
        ? [].concat.apply(graph[word], graph[word].map(getSuccessors))
        : [];
})(word);
return successors;

如果你确定在图中没有圆圈，并且只想要路径初学者的列表，你可以添加以下内容：

var results = [];
for (var word in successors)
    for (var i=0; word in successors && i<successors[word].length; i++)
        delete successors[successors[word][i]];
for (var word in successors)
    results.push([word].concat(successors[word]));
return results;
// becomes:
[
   ["bed","sheets"],
   ["guitar","strings","pickup","car","wheel","tyre"],
   ["rubber","tyre"],
   ["truck","wheel","tyre"]
]