Diese Version des Algorithmus von Kruskal repräsentiert die Kanten mit einer Adjazenzliste. Wie würde ich den Pseudocode ändern, um stattdessen eine Adjazenzmatrix zu verwenden?Kruskal-Algorithmus - Modifizieren zu Matrix-Datenstruktur?
ich Sie dachte, wir müssten das Gewicht der Kanten zum Beispiel (i, j), solange es nicht Null verwenden. Zuweisen der Scheitelpunkte zu i, j. Ich mag auf diesem Pseudo-Code von Kruskals etwas verwirrt sein.
Wie in Henry angegeben, hat der Pseudocode nicht angegeben, welche konkreten Datenstrukturen verwendet werden sollen. Es scheint lediglich, dass die Adjazenzlisten-Darstellung des Graphen in diesem Fall praktischer ist als die Adjazenz-Matrix-Darstellung.
Für die Adjazenzmatrix müssen Sie einfach alle Einträge Ihrer Matrix scannen, um die Kanten des Graphen G in Zeile 4 zu sortieren. Und Sie tun genau dasselbe, wenn Sie die Adjazenzliste verwenden.
In Ihrem Fall können Sie z. B. eine PriorityQueue verwenden, um die Kanten nach Gewicht in nicht abnehmender Reihenfolge zu sortieren und Einträge mit getrennten Scheitelpunkten zu verwerfen. Sie können diese Datenstruktur dann in for-loop in Zeile 5 iterieren.
Im Pseudocode gibt es nichts, das angibt, welche Datenstrukturen verwendet werden müssen. Aber das Sortieren der Kanten nach Gewicht wird in einer Matrix ohne eine Hilfsdarstellung schwierig sein. – Henry