Vorschläge für die einfachsten Algorithmen für einige Graph-Operationen

  

Listen Sie alle Benutzer im Graphen-Netzwerk auf, die einen Abstand X haben

Eine Entfernung X von was? von einem Startknoten oder eine Entfernung X zwischen sich? Kannst du ein Beispiel geben? Dies kann oder kann nicht so einfach sein wie das Ausführen einer BF-Suche oder das Ausführen von Dijkstra.

Angenommen, Sie beginnen an einem bestimmten Knoten und möchten alle Knoten mit den Distanzen X zum Startknoten auflisten, führen Sie einfach BFS vom Startknoten. Wenn Sie einen neuen Knoten in die Warteschlange einfügen möchten, überprüfen Sie, ob die Entfernung vom Startknoten zum Knoten, an dem Sie den neuen Knoten einfügen möchten, vom Gewicht der Kante des Knotens, in den Sie den neuen Knoten einfügen möchten, ist Der neue Knoten ist & lt; = X . Wenn es streng niedriger ist, fügen Sie den neuen Knoten ein und wenn es gleich ist, drucken Sie einfach den neuen Knoten (und fügen Sie ihn nur ein, wenn Sie auch 0 als Kantengewicht haben können).

  

Listen Sie alle Benutzer im Graphen-Netzwerk auf, die einen Abstand X und den Relationstyp

enthalten

Siehe oben. Berücksichtigen Sie den Typ der Beziehung in das BFS: Wenn der Typ des übergeordneten Elements sich von dem des Knotens unterscheidet, den Sie in die Warteschlange einfügen möchten, fügen Sie ihn nicht ein.

  

Berechnen Sie den kürzesten Pfad zwischen zwei Benutzern im Graphen-Netzwerk bei einem Relationstyp

Der Algorithmus hängt von einer Reihe von Faktoren ab:

• Wie oft müssen Sie das berechnen?
• Wie viele Knoten haben Sie?

Da Sie einfach wollen, sind Roy-Floyd und Dijkstra am einfachsten.

• Die Verwendung von Roy-Floyd ist kubisch in der Anzahl der Knoten, also ineffizient. Verwenden Sie dies nur, wenn Sie es sich leisten können, es einmal auszuführen und dann jede Abfrage in O (1) zu beantworten. Verwenden Sie dies, wenn Sie es sich leisten können, eine Adjazenzmatrix im Speicher zu behalten.
• Dijkstra's ist quadratisch in der Anzahl der Knoten, wenn Sie es einfach halten wollen, aber Sie müssen es jedes Mal ausführen, wenn Sie den Abstand zwischen zwei Knoten berechnen wollen. Wenn Sie Dijkstra verwenden möchten, verwenden Sie eine Adjazenzliste.

Hier sind C-Implementierungen: Roy-Floyd und Dijkstra_1 , Dijkstra_2 . Sie können eine Menge auf Google mit "<algorithm name> c implementation" finden.

Edit: Roy-Floyd kommt für 18.000 Knoten nicht in Frage, ebenso wie eine Adjazenzmatrix. Es würde viel zu viel Zeit in Anspruch nehmen und viel zu viel Speicher. Am besten ist es, entweder den Dijkstra-Algorithmus für jede Abfrage zu verwenden, aber vorzugsweise Dijkstra mit einem Heap zu implementieren. Verwenden Sie in den von mir bereitgestellten Links einen Heap, um das Minimum zu finden. Wenn Sie bei jeder Abfrage das klassische Dijkstra ausführen, könnte das auch sehr lange dauern.

Eine weitere Option ist die Verwendung des Bellman-Ford -Algorithmus für jede Abfrage, die geben wird Sie O(Nodes*Edges) Laufzeit pro Abfrage. Dies ist jedoch eine große Überschätzung, wenn Sie es nicht implementieren, wie es Ihnen Wikipedia sagt. Verwenden Sie stattdessen eine Warteschlange, die der in BFS verwendeten ähnlich ist. Wenn ein Knoten seinen Abstand von der Quelle aktualisiert, fügen Sie diesen Knoten wieder in die Warteschlange ein. Dies wird in der Praxis sehr schnell sein und auch für negative Gewichte funktionieren. Ich schlage vor, Sie verwenden entweder diese oder die Dijkstra mit Heap, da klassische Dijkstra eine lange Zeit auf 18 000 Knoten dauern kann.

  

Berechnen Sie die maximale Entfernung zwischen zwei Benutzern im Graphen-Netzwerk

Der einfachste Weg ist Backtracking: Versuche alle Möglichkeiten und behalte den längsten gefundenen Pfad. Dies ist NP-vollständig , so dass polynomiale Lösungen nicht existieren.

Das ist wirklich schlimm, wenn Sie 18 000 Knoten haben, ich kenne keinen Algorithmus (einfach oder nicht), der für so viele Knoten einigermaßen schnell arbeitet. Berücksichtigen Sie die Approximation mit Hilfe von Greedy-Algorithmen. Oder vielleicht hat Ihr Diagramm bestimmte Eigenschaften, die Sie nutzen könnten. Zum Beispiel, ist es ein DAG (Directed Azyklic Graph)?

  

Berechnen Sie die am weitesten entfernten verbundenen Benutzer im Graphen-Netzwerk

Bedeutung Sie möchten den Durchmesser des Graphen finden. Der einfachste Weg, dies zu tun, ist, die Abstände zwischen den beiden Knoten zu finden (die kürzesten Pfade aller Paare - entweder Roy-Floyd oder Dijkstra zwischen jeweils zwei Knoten ausführen und die beiden mit der maximalen Entfernung auswählen).

Auch hier ist es sehr schwierig, schnell mit der Anzahl der Knoten und Kanten zu arbeiten. Ich fürchte, Sie haben bei diesen letzten beiden Fragen kein Glück, es sei denn, Ihr Diagramm verfügt über spezielle Eigenschaften, die ausgenutzt werden können.

  

Glauben Sie, es würde helfen, wenn ich den Graphen in eine Adjazenzmatrix "umwandelte", um das Gewicht und den Relationstyp der Links darzustellen? Wäre es einfacher, den Algorithmus anstelle der verknüpften Listen auszuführen?Ich könnte leicht eine Funktion implementieren, um diese Konvertierung bei Bedarf durchzuführen. Ich sage das, weil ich das Gefühl hatte, es wäre einfacher, nachdem ich ein paar Seiten über das Thema gelesen habe, aber ich könnte falsch liegen.

Nein, Adjazenzmatrix und Roy-Floyd sind eine sehr schlechte Idee, es sei denn, Ihre Anwendung zielt auf Supercomputer ab.

Dies setzt voraus, dass O(E log V) eine akzeptable Laufzeit ist. Wenn Sie etwas online tun, ist dies unter Umständen nicht der Fall, und dazu würden einige leistungsfähigere Maschinen benötigt.

• Listen Sie alle Benutzer im Graphen-Netzwerk auf, die eine Distanz X
haben

Der Algorithmus von Djikstra eignet sich gut für die einmalige Verwendung. Sie können das Ergebnis für zukünftige Verwendung speichern, mit einem linearen Scan durch alle Vertices (oder besser noch, sortieren und binäre Suche).

• Listen Sie alle Benutzer im Graphen-Netzwerk auf, die eine Entfernung X und die Art der Beziehung
enthalten

Kann fast wie oben sein - benutze einfach eine Funktion, bei der das Gewicht unendlich wäre, wenn es nicht die richtige Relation hat.

• Berechnen Sie den kürzesten Pfad zwischen zwei Benutzern im Graphen-Netzwerk bei einem Relationstyp

Wie oben, im Wesentlichen, bestimmen Sie nur früh, wenn Sie die beiden Benutzer übereinstimmen. (Alternativ können Sie sich "in der Mitte treffen" und vorzeitig beenden, wenn Sie jemanden auf dem kürzesten Pfad finden, der den Baum überspannt)

• Berechnen Sie die maximale Entfernung zwischen zwei Benutzern im Graphen-Netzwerk

Längster Pfad ist ein NP-vollständiges Problem .

• Berechnen Sie die am weitesten entfernten verbundenen Benutzer im Diagrammnetzwerk

Dies ist der Durchmesser des Graphen, über den Sie in Math World nachlesen können.

Was die Frage der Adjazenzliste und der Adjazenzmatrix anbelangt, hängt es davon ab, wie dicht das Diagramm ist. Wenn Sie Ergebnisse zwischenspeichern möchten, ist die Matrix möglicherweise die beste Methode.