2d-Array und Graphentheorie
-
Ich möchte aus einem 2d Array einen Graphen erzeugen. Das Array repräsentiert einen zusammenhängenden Graphen. Alle Felder die in dem Array beispielsweise auf 1 gesetzt sind, gelten als verbunden, sofern diese direkt aneinander grenzen.
Nun möchte ich zum Beispiel mit Hilfe der Breitensuche die kürzeste Verbindung zweier Punkte finden(für diesen benötige ich den Graphen).
Nun zu meiner konkreten Frage: Die Graphentheorie spielt in der Informatik eine große Rolle. Daraus folgere ich, dass es genau für dieses Problem schon fertige gut durchdachte Lösungen gibt.
Mein Ansatz wäre eine Klasse Knoten. Jeder Knoten würden alle benachbarten Knoten in einem Vector enthalten(wenn diese im Array gesetzt sind). Dabei verzichte ich dann expliziet auf die Kanten. Dann könnte ich von einem Ausgangsknoten den Weg zu einem Zielknoten finden.
Dieser Lösungsansatz kommt mir nicht grad sehr durchdacht vor. Welche anderen Lösungsansätze gibt es, die sich evtl. schon etabliert haben?
Danke für eure Mühen!
-
Nur weil es ein Weit verbreitetes Model ist, heißt es nicht, dass es eine allgemeingültige Bibliothek oder so gibt. Man kann Graphen darstellen wie man will, je nach Anwendung.
Dein Ansatz ist doch gar nicht so falsch.
Was du noch brauchst ist eine Variable, die markiert, dass ein Knoten schon besucht hast.
Wenn du auf Kanten verzichtest gehts du bei deiner Lösung davon aus, dass alle Knoten gleichweit von einander weg sind und du musst beim Hinzufügen/Löschen einer Kante 2 Konten bearbeiten.Meine Ansatz mit deinen Mitteln wär:
* Du hast drei Arten von Knoten
1. Knoten wo du noch nicht warst
2. Knoten die du grad erreicht hast
3. Knoten die du schon besucht hast und nicht mehr betrachten brauchst.
a) Du fügst deinen Startknoten zu Menge 2 und markiere ihn
b) Wähle einen markierten Konten(A) aus Menge 2
c) Suchst alle Knoten die vom Knoten(A) erreichbar sind und in Menge 1 sind
d) gefundene Knoten zu Menge 2 hinzufügen
e) Knoten(A) zu Menge 3
f) Wenn es in Menge 2 keine markierten Knoten mehr gibt alle Konten in Menge 2 markieren
g) Wenn noch Knoten in Menge 1 und Menge 2 sind gehe zu BJa so könnte man das machen