Habe jetzt heute im Gespräch mit nem Arbeitskollegen eine einigermaßen zufriedenstellende Lösung gefunden. Vielleicht ist es ja für den ein oder anderen interessant.
Die beste Lösung wäre es eine Indizierung für die Knoten zu finden. Bei dem Problem mit den Koordinaten können natürlich die Koordinaten als Index in einer Hashmap oä benutzt werden. Beim Rubiks-Cube könnte man den Index aus den Feldern und Farben zusammensetzen. Die Idee(Die ohne mathematischen Beweis sinnvoll erscheint) setzt sich folgendermaßen zusammen:
Jedes Feld des Würfels stellt eine Stelle der Zahl dar. Jede Farbe bekommt einen Zahlenwert. Sagen wir mal Rot ist 1, Blau ist 2 und so weiter. Ist stelle 1 rot, ist die erste Zahl vom Index also 1. Ist die zweite Stelle blau kommt an die zweite Stelle eine Zwei. Ist die dritte wieder rot würde an Stelle 3 eine 1 kommen. Das macht man nun für jedes Feld des Würfels und hat hinterher einen Index mit 54 Stellen. Ist natürlich nicht besonders schön, liefert aber eindeutige Indizes. Die Werte müssen natürlich nicht direkt als eine Zahl gespeichert werden(Integer wäre dort ja eh nicht geeignet
), könnten jedoch auf mehrere kleinere Integer aufgesplittet werden. Wie auch immer man das jetzt genau umsetzen möchte. Ein bisschen Kreativität soll ja bleiben
So hätte man für eine Überprüfung eine Laufzeit von O(1).
Ansonsten könnte man die Liste aller Knoten durchlaufen und überprüfen ob der Knoten schon vorhanden ist. Habe da nochmal drüber nachgedacht und die Laufzeit hierfür wäre O(n) bei n Knoten, was auch ok wäre
Naja vielleicht hilfts ja irgendjemandem weiter.