Filter Graph Knoten, die eine Verbindung mit einem Kandidaten haben

Ich möchte eine Liste filter so, dass ich nur die Knoten bekommen würde, die eine Verbindung haben, entweder direkte oder indirekte mit einem KandidatenFilter Graph Knoten, die eine Verbindung mit einem Kandidaten haben

var candidate = 1; 
    var data = [ 
    { source: 1, target: 2 }, // is connected with 1 
    { source: 2, target: 3 }, // is connected with 1 
    { source: 6, target: 9 }, // no connection 
    { source: 12, target: 15 }, // no connection 
    { source: 3, target: 2 }, // is connected with 1 
    { source: 5, target: 3 }, // is connected with 1 
    ]

Welche Art von Algorithmus suche ich?

Die Sprache von Interesse ist JavaScript - AFAIK einige Sprachen einen Algorithmus in einer anderen Art und Weise

Quelle

2016-09-27 Nicholas Kyriakides

Breitensuche als andere umsetzen würde:

eine Liste Pflegen von „Maybe“ Kanten (initialisiert mit dem angegebenen Liste), eine Liste von "Verbundenen" Kanten (initialisiert leer) und eine Liste von Knoten (initialisiert, um nur den "Kandidaten" zu enthalten).

Entfernen Sie einen Knoten aus der Knotenliste.
Iterieren Sie durch die Maybe-Liste und suchen Sie nach diesem Knoten. Wenn eine Kante diesen Knoten enthält, kopieren Sie den anderen Knoten in die Knotenliste und verschieben Sie diese Kante in die Liste Verbunden.
Fahren Sie fort, bis die Knotenliste leer ist.

Quelle

2016-09-27 23:32:59 Beta

'Entfernen Sie einen Knoten aus der Liste der Knoten.Möchten Sie die vielleicht Liste? Die Knotenliste würde zunächst nur den Kandidaten –

@NicholasKyriakides enthalten: Nein, ich meine die Knotenliste. Es enthält zunächst nur den Kandidaten; Entferne diesen und durchsuche die Maybe-Liste, um nach dem Knoten zu suchen. Wenn die Knotenliste am Ende leer ist, sind Sie fertig: Keine der Kanten ist mit dem Kandidaten verbunden. – Beta

Filter Graph Knoten, die eine Verbindung mit einem Kandidaten haben

Antwort

Verwandte Themen