Graph representation

Question

Given graph, how could i represent it using adj matrix?. I have read lots of tutorials, post, slides, etc but i cant get my head round it, i just need that little push.

Answer 1

Every letter-number combination is one node in your graph, i.e., from A0, A1, A2, ... to F5, F6, F7. Your graph has 48 (8 columns times 6 rows in your maze) nodes, so you'll need a 48x48 matrix. If you treat it as boolean, you'll set all fields to false except the ones where there is a connection between two nodes, e.g. A0 to A1 would mean that the A0 row has a true value in the A1 column, and vice versa (because your graph is undirected).

Answer 2

Here's my attempt for the first horizontal line of the maze:

   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

So you can see from this that your going to end up with a symmetrical matrix due to the undirected nature of your edges and that its going to be sparsely populated.

EDIT: Matrix vs Lists

The wikipedia entry for adjacency list has some good points on the algorithmic benefits of each.

EDIT:

Wikipedia entry for Adjacency Matrix :+)

Answer 3

Another way would be to have 2 boolean matrices named Hor and Ver to track the possibility of horizontal and vertical movement respectively.

Hor Matrix: Dimension:6x9
[X,YZ] represents the possiblity of a horizontal movement from [X,Y] to [X,Z] on the real board.
-1 represents the boundary

example: [A,01] is true and so is [F,-10]. But [B,23] is false.

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

Similarly

Ver Matrix: Dimension: 7x8
[XY,Z] represents the possiblity of a vertical movement from [X,Z] to [Y,Z] on the real board.
Capital o in the row represent boundary.
example: [DE,0] is true and so is [BC,7]. But [CD,0] is false.

    0 1 2 3 4 5 6 7

OA
AB
BC
CD
DE
EF
FO