javascript - 将邻接列表转换为无向图链接的高性能方法

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 处理重复项。