1. Originally Posted by iamnew
oo no i don't understand whats going on . Iam confused with maze representation. can you guys please explain in the most simplest way. Iam kind of a NOOB.
Alright, first off, is this for a homework assignment? That's okay, we can still help you, but it makes a big difference with regard to what you are trying to accomplish. I think both those definitions make sense, would serve a purpose, and you could write a program to derive such a thing from a graph which describes a maze.

If it's not homework, explain why you are doing this. Also: do you understand how to implement a graph in a computer program?

2. An adjacency list is just a list of all the adjacent squares. So the list for the maze you posted might start ((A0,A1), (A2,A3), (A4,A5), (A1,B1), (A2,B2), (A4,B4), (A5,B5), (A6,B6), (A7,B7), (B0,B1), (B1,B2), ......) Or you can sort by vertex and keep a list, for every square, which other squares are adjacent. So the list for A0 would be (A1); for A1 it would be (A0, B1); for A2 it would be (A3, B2); etc.

3. Isn't the adjacency list representation the best way of solving the maze problem. Since it requires substantially lesser amount of nodes.

4. Originally Posted by iamnew
Isn't the adjacency list representation the best way of solving the maze problem. Since it requires substantially lesser amount of nodes.
Compared to what? You probably wouldn't be storing actual whatever-you're-using-for-your-squares in your lists, but pointers.

In any event, you need to work out what your algorithm is for getting through the maze; that will probably suggest a data structure for storing your maze.

5. If you want to use this to solve the maze, I would think the second kind (a list for each node) would be more useful. Like tabstop says, you need some idea of how you are going to solve the maze.

But if that is your goal (to solve the maze), an adjacency list is probably not necessary at all since that information is encapsulated in a graph structure anyway.

6. Oh well i have to use a graph representation anyway. Now in the adjacency representation a node is the point at which a decision has to be taken in the maze. So since in the entire maze has only a few decision points only a few nodes are needed.

7. You're going to have 48 nodes no matter what, since that's how many squares there are.

8. Originally Posted by iamnew
Oh well i have to use a graph representation anyway. Now in the adjacency representation a node is the point at which a decision has to be taken in the maze. So since in the entire maze has only a few decision points only a few nodes are needed.
Sure, but a graph node (for a 2D maze) looks (something) like this:
Code:
```struct node {
int ID;  // not necessary
struct node *north;
struct node *south;
struct node *east;
struct node *west;
}```

Also, you need all the nodes, not just the decision points, or the "decision points" will have no relation.

9. Originally Posted by MK27
Sure, but a graph node (for a 2D maze) looks (something) like this:
Code:
```struct node {
int ID;  // not necessary
struct node *north;
struct node *south;
struct node *east;
struct node *west;
}```

Also, you need all the nodes, not just the decision points, or the "decision points" will have no relation.
Why there will be no relation. The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.

10. Originally Posted by iamnew
Why there will be no relation. The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.
How do you know what the "right" decision points are until you solve the maze? If you're going by the unsolved version, every square is then a "decision point".

11. >>The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.
Good point. I guess you could describe a maze that way too. It still renders the "adjacency list" question superfluous. I also don't see the point in weighting the edge, unless you are looking for the shortest route.

Actually using a weighted edge introduces a form of complication such that I don't think this will be an improvement over graphing all the nodes UNLESS you are thinking of a maze with many long straight corridors. Even then, I don't think it is necessarily better. Maybe.

12. okay the other way that iam thinking of is using a boolean 2D array. Is this a good method over adjacency matrix? Can i do graph traversals using a boolean 2D array?

13. A boolean 2D array is an adjacency matrix.

14. I feel like using a adjacency list and taking nodes as the decision point is not very good because we have to compute the edge value. I like if all the computing is done by the PC.

15. SO with which representation should go forward? IS it the matrix or list? Iam exhausted now. I feel like giving up.