Erzeuge eine Adjazenzmatrix für ein gewichtetes Diagramm
Ich versuche, Floyd-Warshall-Algorithmus zu implementieren. Um dies zu tun, muss ich einen adjacency matrix eines gewichteten Graphen einrichten. Wie würde ich das machen? Ich kenne die Werte und habe ein Bild der gewichteten Grafik beigefügt. Ich habe versucht, nach einigen Online-Beispielen zu suchen, aber ich kann nichts finden. Ich verstehe Floyd-Warshall-Algorithmus Ich brauche nur Hilfe, damit es eingerichtet wird, damit ich es implementieren kann. Hier ist eine, die ich vorher gebaut habe, aber ich musste keine spezifischen Werte verwenden.
Code:
%Vor%Hier ist der spezifische Graph zur Hand:
Hier ist ein Bild der Matrix, die ich erstellen muss. Sorry für die schreckliche Qualität ...
1 Antwort
Sie scheinen also nicht mit Graphen vertraut zu sein, werfen Sie einen Blick auf Wikipedia. Suchen Sie auch nach einigen Bildern, es wird einfacher zu verstehen.
Ein bisschen Konzept
Ihr Bild kann als Graph dargestellt werden. Im Allgemeinen werden Diagramme mit 2 grundlegenden Arten von Elementen implementiert, Nodes und Links (manchmal auch als Arcs bezeichnet).
A Node repräsentieren die Buchstaben in Ihrem Bild, sie wären A, B, C usw.
Ein Arc oder Link , ist die Linie, die zwei Knoten verbindet, wenn Sie die Verbindung zwischen H und L betrachten, die eine Verbindung zwischen den beiden haben, in einem gewichteten Graph haben verschiedene Verbindungen unterschiedliche Gewichte.
Lösen Sie Ihr Problem - Teil 1
Was wir tun müssen, ist, Ihr Bild als Grafik im Code darzustellen. Beginnen wir also mit der Erstellung der Basiselemente Node und Arc :
Knoten
Ein Knoten hat Name , so dass wir den Knoten identifizieren können. Und ein Knoten kann mit anderen Knoten verbunden sein, wir könnten eine Sammlung von Knoten verwenden, aber Ihre ist ein gewichteter Graph, also muss jede der Verbindungen durch den verknüpften Knoten und dessen Gewicht dargestellt werden. Daher verwenden wir eine Sammlung von Bögen.
Bogen
Wirklich einfache Klasse, enthält die verknüpften Knoten und das Gewicht der Verbindung:
%Vor%Diagramm
Graph ist eine Art Wrapper-Klasse für Organisationszwecke. Ich habe auch eine Wurzel für das Diagramm deklariert, wir verwenden es nicht, aber es ist in mehreren Fällen nützlich:
%Vor%Lösen Sie Ihr Problem - Teil 2
Jetzt haben wir die gesamte Datenstruktur, um das Diagramm zu halten, füllen wir es mit einigen Daten. Hier ist ein Code, der ein Diagramm ähnlich Ihrem Würfelbild initialisiert. Es ist langweilig und langweilig, aber in realen Fällen wird das Diagramm dynamisch erstellt:
%Vor%Lösen Sie Ihr Problem - Teil 3
Wir haben also einen vollständig initialisierten Graphen, lassen Sie uns die Matrix erstellen. Die nächste Methode erstellt eine Matrix aus zwei Dimensionen, n mit n, wobei n die Anzahl der Knoten ist, die wir aus der Graphklasse erhalten. Für jeden der Knoten suchen wir, ob sie eine Verbindung haben, wenn sie eine Verbindung haben, füllte sie die Matrix an der richtigen Stelle. Schau, dass du in deinem Adjazenzmatrix-Beispiel nur 1 s hast, hier gebe ich das Gewicht des Links an, das habe ich so ausgedrückt, also hat es keinen Sinn, einen gewichteten Graphen zu haben!
Fertig
Das ist getan, Sie haben Ihre gewichtete Adjazenzmatrix, eine Möglichkeit, es zu drucken:
%Vor%Was gibt uns die folgende Ausgabe:
%Vor%Tags und Links c# data-structures graph adjacency-matrix