轉換鄰接表來鏈接，無向圖

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

您可以將一個絃樂陣列作爲該集合的值，因爲只有排序值的數組正在使用嚴格模式進行檢查。

原始數據類型，如字符串效果最好。

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))