将无向图的邻接表转换为链表的有效方法

Question

我有一个邻接表，如下所示：

const list = [
 [1, 6, 8],
 [0, 4, 6, 9],
 [4, 6],
 [4, 5, 8],
 // ...
];

我需要为一个没有重复的无向图创建一组链接(示例如下)。像[0,1]和[1,0]这样的链接被认为是重复的。

const links = [
 [ 0, 1 ], // duplicates
 [ 0, 6 ],
 [ 0, 8 ],
 [ 1, 0 ], // duplicates
 [ 1, 4 ],
 // ...
]

现在我这样做：

const links = new Set;
const skip = [];

list.forEach( (v, i) => {
    v.forEach( j => {
        if (skip.indexOf(j) === -1) {
            links.add([i, j]);
        }
    })
    skip.push(i);
})

我想知道是否有更好的模式来解决大规模数组上的这类任务。

Answer 1

您可以对链接元组值进行排序，跳过检查skip.indexOf(j)并让Set处理重复项。

Answer 2

您可以将字符串数组作为集合的值，因为只有排序值的数组在集合中使用严格模式进行检查。

像string这样的原始数据类型效果最好。

​

var list = [[1, 6, 8], [0, 4, 6, 9], [4, 6], [4, 5, 8]],
    links = new Set;

list.forEach((v, i) => v.forEach(j => links.add([Math.min(i, j), Math.max(i, j)].join())));
   
console.log([...links]);

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

​

Answer 3

您可以使用一个对象来存储已经使用过的value: index，然后在添加到数组之前检查该对象。

​

const list = [[1, 6, 8],[0, 4, 6, 9],[4, 6],[4, 5, 8],];
var o = {},r = []

list.forEach(function(e, i) {
  e.forEach(function(a) {
    if (o[i] != a) {
      r.push([i, a])
      o[a] = i
    }
  })
})

console.log(JSON.stringify(r))

​

使用ES6箭头函数，您可以像这样编写相同的代码。

​

const list = [[1, 6, 8], [0, 4, 6, 9], [4, 6], [4, 5, 8],];
var o = {}, r = []

list.forEach((e, i) => e.forEach(a => o[i] != a ? (r.push([i, a]), o[a] = i) : null))
console.log(JSON.stringify(r))

​