Java: Datenstruktur für den minimalen Spanning Tree

Question

Mein Projekt ist die Implementierung eines minimalen Spannbaums mit Java. Ich beabsichtige, Prims Algorithmus zu verwenden, um die Aufgabe zu erledigen.

Die Definition des Graphen ist G = (V, E), wobei V die Menge der Pins ist, E die Menge der möglichen Verbindungen zwischen Paaren von Pins und für jede Kante (u, v) in E wir haben ein Wiegen w (u, v), das die Kosten angibt, um u und v zu verbinden.

Meine Idee ist, zwei hashmaps zu verwenden. Zuerst hätte Pin als Schlüssel und eine Liste von Nachbarn als Wert. Die zweite Hashmap würde die Liste der Kanten (u, v) als Schlüssel nehmen, und der Wert wäre sein Gewicht.

Was ist Ihrer Meinung nach der beste Weg, um das Diagramm zu speichern?

Answer 1

Graphen sind in der Regel (ohne Berücksichtigung des Algorithmus mit den Diagrammen verwendet wird) gespeichert, wie entweder:

• Adjazenzlisten,
• Adjazenzmatrizen,
• Inzidenzlisten,
• Inzidenzmatrizen.

Alle haben ihre Vor- und Nachteile in Bezug auf die Speicherauslastung und die Zeit, um sie zu durchlaufen. Wikipedia hat eine große Aufzählung auf Graphdarstellungen in Computern.

Answer 2

Schauen Sie auf wikipedia. Sie haben verschiedene Datenstrukturen zur Verfügung sowie die geerbten Komplexitäten

Answer 3

Für Kruskals und Prims Minimum-Spanning-Tree-Algorithmen reicht die Adjazenzlisten-Darstellung des Graphen aus. Es ist effizienter in der Speichernutzung als Matrizen-Ansatz. Es ist also eine gute Wahl in Ihrem Fall.