Графическое представление

Question

Учитывая график, как я мог бы представить его с помощью прилегающей матрицы ?. Я прочитал много уроков, постов, слайдов и т. Д., Но я не могу обойти это, мне просто нужен небольшой толчок.

альтернативный текст http://i39.tinypic.com/10xu4hv.png

Answer 1

Вот моя попытка первой горизонтальной линии лабиринта:

   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

Итак, из этого вы можете видеть, что ваша симметричная матрица будет в конечном итоге из-за ненаправленной природы ваших ребер и что она будет малонаселенной.

РЕДАКТИРОВАТЬ: Матрица против списков

Запись в Википедии для списка смежности имеет несколько хороших моментов в отношении алгоритмических преимуществ каждого.

РЕДАКТИРОВАТЬ:

Запись в Википедии для матрицы смежности : +)

Answer 2

Каждая комбинация букв и цифр - это один узел на вашем графике, то есть от A0, A1, A2, ... до F5, F6, F7. Ваш график имеет 48 (8 столбцов и 6 строк в вашем лабиринте) узлов, поэтому вам понадобится матрица 48x48. Если вы рассматриваете это как логическое значение, вы установите все поля в false, кроме тех, где есть связь между двумя узлами, например От A0 до A1 будет означать, что строка A0 имеет истинное значение в столбце A1, и наоборот (потому что ваш график не направлен).

Answer 3

Другим способом было бы иметь 2 boolean матрицы с именами Hor и Ver для отслеживания возможности горизонтального и вертикального перемещения соответственно.

Hor Matrix: Размер: 6x9
[X,YZ] представляет возможность горизонтального перемещения от [X,Y] до [X,Z] на реальной доске.
-1 представляет границу

пример: [A,01] - это true, как и [F,-10]. Но [B,23] это false.

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

Аналогично

Ver Matrix: Размер: 7x8
[XY,Z] представляет возможность вертикального перемещения от [X,Z] до [Y,Z] на реальной доске.
Capital o в строке обозначают границу.
пример: [DE,0] - это true, а также [BC,7]. Но [CD,0] - это false.

    0 1 2 3 4 5 6 7

OA
AB
BC
CD
DE
EF
FO