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

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 2

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).