3D-Array-Traversierung in unterschiedlicher Reihenfolge

Dies funktioniert, indem Sie ein Diagramm erstellen, in dem jede Zelle ein Knoten ist. Da der Graph die Form eines Würfels hat, muss jeder Knoten eine Verbindung zu seinem Nachbarn X, Y und Z haben. Der erste Schritt besteht darin, den Graphen zu erstellen, indem dem Programm die Beziehung zwischen den Nachbarknoten zugeführt wird. Zum Beispiel sollten wir dem Programm eine Eingabe geben, die besagt, dass der Knoten Null mit dem Knoten 1 verbunden ist, usw. Nachdem wir dem Programm mitgeteilt haben, wie die Knoten verbunden sind, um den Würfel zu bilden, ist es leicht, darüber nachzudenken. Ein beliebter Algorithmus zum Traversieren von Graphen heißt Breathth First Traversal (BFT), dieser Algorithmus erlaubt es, Knoten auf eine verteilte Weise zu durchlaufen. Wenn Sie beispielsweise einen Baum haben, bei dem es sich um eine Art von Graphen handelt, wird zuerst die Wurzel gedruckt, dann wird jede Ebene einzeln gedruckt, so dass die Baumstruktur vom Startpunkt aus durchquert wird, indem sie sich gleichmäßig ausbreitet Geäst. In Ihrem Beispiel, einen Würfel von der Mitte bis zu den Ecken zu überqueren, ist genau das, was BFT für Sie tun kann. In diesem Fall beginnt BFT von der Mitte aus und beginnt, die Knoten Fläche für Fläche zu durchlaufen, und da wir vom Mittelpunkt ausgehen, wird die Ausbreitung eine Kugelform annehmen.

Was ist BFT
BFT muss eine Datenstruktur namens Queue verwenden, die eine First-In-First-Out-Liste ist. Zuerst bieten wir der Warteschlange den Startpunkt an und wir markieren ihn als besucht, was bedeutet, dass er in die Warteschlange eingetreten ist und es nicht erlaubt ist, später in den Durchlauf einzutreten. Dann wenden wir einen Proceder an, der den Hauptknoten abfragt, ihn als besucht markiert und seine nicht besuchten Nachbarn anbietet. Derselbe Prozess wird immer wieder ausgeführt, bis alle Knoten besucht sind und daher die Warteschlange leer ist. Der Grund dafür, dass wir hier eine Warteschlange verwenden, besteht darin, dass Knoten in ausgewogener Weise durchlaufen werden können. In diesem Cube-Traversal-Programm wird das Anbieten des mittleren Knotens folgen, indem es aus der Warteschlange abgefragt wird und seine 6 Nachbarn anbietet (im Falle von & gt; = 3x3x3-Würfel). Dann wird jeder dieser Nachbarknoten in der Reihenfolge des Eingangs abgefragt und seine Nachbarn werden am Ende der Warteschlange angeboten. Der Proceeder läuft so lange, bis kein unbekannter Nachbar mehr übrig ist.

Code Erläuterung:
Zuerst müssen wir die Größe des Würfels kennen. Ein Würfel von 3x3x3 bedeutet, dass wir 27 Knoten erzeugen sollten. Ich habe eine Methode namens generateCubeGraph() erstellt, die eine Eingabezeichenfolge generiert, um das Programm über die Beziehung zwischen benachbarten Knoten zu informieren. Ein Beispiel für die Rückgabe der Ausgabe mit dieser Methode:

Die ersten beiden Werte sind die Anzahl der Knoten bzw. die Anzahl der Links / Kanten zwischen den Nachbarknoten. Der Rest der Linien ist die Verbindung zwischen Knoten. Zum Beispiel sagt die erste Zeile, dass der Knoten Null mit dem Knoten 1 verbunden ist, etc ... Beachten Sie, dass dies ein ungerichteter Graph ist. Wenn das Programm die Verbindung zwischen Knoten speichert, wird es von Knoten x zu Knoten y und von Knoten y nach gespeichert Knoten x.
Nach dem Generieren der Eingabe speichert die Methode build() die Verknüpfungen zwischen den Knoten in einer Adjazenzliste. Ein weiteres Array wird erstellt, um zu zählen, wie viele Kanten für jeden Knoten erstellt wurden.
Nach dem Speichern der Links müssen wir nur noch das Cube-Diagramm mit dem BFT-Algorithmus durchlaufen. Überprüfen Sie die obige Beschreibung, wie es funktioniert und lesen Sie die Implementierung, um mehr darüber zu erfahren, wie es funktioniert.
Die Druckmethoden sind optional, sie helfen bei der Implementierung und in der Beschreibung, wie der Code funktioniert.

Dieses Bild zeigt, wie ich die Knoten in einem Würfel von 3x3x3 Knoten nummeriert habe. Außerdem habe ich ein Beispiel hinzugefügt, um zu zeigen, wie ein Knoten mit seinem Nachbarn X, Y und Z verbunden ist (am unteren Rand des Bildes).

Hier ist der Code für einen Würfel mit 3 x 3 x 3 Knoten in JAVA: (Sie können die Anzahl der Knoten pro Seite ändern, indem Sie die Variable sideNode ändern)

Ausgabe

Verknüpfen Sie, um zu überprüfen, wie es in 3D funktioniert (Sie müssen die Knoten in der verarbeiteten Knotenreihenfolge färben, und Sie können die Knotennummer erhalten, indem Sie die Ebenenausgabe für jede Knotennummer sehen):

3D-Modell für einen 5 x 5 x 5 Würfel

Ich wäre versucht, das Offensichtlichste zu tun: ein Konnektivitätsdiagramm (das durch die Array-Position implizit sein kann) und eine Bucket-Sortierung.

Nehmen Sie bei jeder Iteration eine beliebige Zelle aus dem Bucket mit der höchsten Nummer. Entfernen Sie für jeden seiner Nachbarn, die nicht als bereits verarbeitet markiert sind, diese aus ihrem aktuellen Bucket und fügen Sie sie in den nächsten Bucket ein. Markieren Sie diese Zelle dann als verarbeitet und entfernen Sie sie aus ihrem Bucket.

Wenn Sie eine strikte Reihenfolge von innen nach außen wünschen, wählen Sie aus der Zelle mit der höchsten Nummer die Zelle aus, die der Mitte am nächsten liegt. Wenn Sie diesen Test anwenden möchten, ist es wahrscheinlich am cleversten, den Bucket-Inhalt ungefähr in der richtigen Reihenfolge zu halten. Es fühlt sich an, als würde man eine geordnete Liste in jedem Bucket und eine Liste von Zellen, die noch nicht in die geordnete Liste eingefügt wurden, machen und eine Just-in-Time-Merge-Sortierung mit der bekannten In-Order-Liste nur beim letzten Merge-Schritt machen .

Habe ich das Problem richtig verstanden?