Performante Weg Adjazenzliste auf Links für ungerichteten Graphen zu konvertieren

Question

Ich habe eine Adjazenzliste wie unten:

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

Ich brauche eine Reihe von Links zu einem ungerichteten Graphen ohne Duplikate erstellen (Beispiel unten). Solche Verbindungen wie [0,1] und [1,0] gelten als Duplikate.

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

Im Moment mache ich es so:

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

Ich frage mich, ob es ein besseres Muster ist diese Art von Aufgabe auf massive Arrays zu lösen.

Answer 1

Sie können Ihre Link Tupel Werte sortieren, überspringen Sie die Prüfung skip.indexOf(j) und lassen Sie Set kümmern sich um die Duplikate.

Answer 2

Sie könnten ein String-Array als Wert für die für die Menge nehmen, da ein Array mit nur sortierten Werten im strikten Modus im Set überprüft wird.

Ein primitiver Datentyp wie String funktioniert am besten.

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

Sie ein Objekt verwenden können value: index zu speichern, die bereits verwendet wurde und dann das Objekt bevor er zu Array hinzufügen.

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

Mit ES6 Pfeil Funktionen Sie das gleiche wie dieses schreiben kann.

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