Grafische Darstellung

Question

Wie könnte ich ein gegebenes Diagramm mit Hilfe einer Adj-Matrix darstellen?

Answer 1

Hier ist mein Versuch für die erste horizontale Linie des Labyrinths:

   A0 A1 A2 A3 A4 A5 A6 A7
A0 0  1  0  0  0  0  0  0
A1 1  0  0  0  0  0  0  0
A2 0  0  0  1  0  0  0  0
A3 0  0  1  0  0  0  0  0
A4 0  0  0  0  0  1  0  0
A5 0  0  0  0  1  0  0  0
A6 0  0  0  0  0  0  0  0
A7 0  0  0  0  0  0  0  0

Daraus können Sie ersehen, dass Sie aufgrund der ungerichteten Natur Ihrer Kanten eine symmetrische Matrix erhalten und dass diese nur spärlich besiedelt sein wird.

EDITAR: Matrix vs. Listen

Der wikipedia-Eintrag für Adjazenzliste hat einige gute Punkte zu den algorithmischen Vorteilen der beiden.

EDITAR:

Wikipedia-Eintrag für Adjacency Matrix :+)

Answer 2

Jede Buchstaben-Zahlen-Kombination ist ein Knoten in Ihrem Diagramm, d.h. von A0, A1, A2, ... bis F5, F6, F7. Dein Graph hat 48 (8 Spalten mal 6 Zeilen in deinem Labyrinth) Knoten, also brauchst du eine 48x48-Matrix. Wenn Sie sie als boolesche Matrix behandeln, setzen Sie alle Felder auf false, außer denen, bei denen eine Verbindung zwischen zwei Knoten besteht, z. B. würde A0 zu A1 bedeuten, dass die Zeile A0 einen wahren Wert in der Spalte A1 hat und umgekehrt (weil Ihr Graph ungerichtet ist).

Answer 3

Eine andere Möglichkeit wäre, dass 2 boolean Matrizen namens Hor y Ver um die Möglichkeit einer horizontalen bzw. vertikalen Bewegung zu erfassen.

Hor Matrix : Dimension: 6x9
[X,YZ] stellt die Möglichkeit einer horizontalen Bewegung von [X,Y] à [X,Z] auf dem echten Brett.
-1 stellt die Grenze dar

Beispiel: [A,01] es true und so ist [F,-10] . Aber [B,23] es false .

   -10 01 12 23 34 45 56 67 7-1
A
B
C
D
E
F

Ähnlich

Ver Matrix : Dimension: 7x8
[XY,Z] stellt die Möglichkeit einer vertikalen Bewegung von [X,Z] à [Y,Z] auf dem echten Brett.
Capital o in der Zeile stehen für die Begrenzung.
Beispiel: [DE,0] es true und so ist [BC,7] . Aber [CD,0] es false .

    0 1 2 3 4 5 6 7

OA
AB
BC
CD
DE
EF
FO