# Represent Maze

This is a discussion on Represent Maze within the C++ Programming forums, part of the General Programming Boards category; How can i represent this maze using a adjacency list. Please help....

1. ## Represent Maze

How can i represent this maze using a adjacency list.

2. You need to decide how to label each point, since you cannot simply use a 2D matrix and call it a 1D list. That's probably important, unless you want to presume the list is in a certain order and refers to a maze of a specific size (also possible).

Using standard C datatypes: an array of structs, the struct would contain the label and a pointer to an array of pointers to adjacent points. You could use linked list instead of either or both arrays.

Using the C++ STL: use something like a
Code:
`map<string,vector<string> >`
Here the strings would be labels for the points (eg. "1,3")

3. in the adjacency list representation do i have to have nodes for each square box?

4. If you're using an adjacency list, then every node in the list represents two square boxes that are connected.

5. Yes, the list is a list of each node/point in the maze, together with a list of all it's adjacent nodes. So a C struct might look like:
Code:
```typedef struct _point {
char[8] label;
} point;```
Since in a 2D maze a point can have at most 4 adjacent points. If less, set the remaining pointers in the adj array to NULL. You need an array of these:
Code:
`point[48];`
in order for it to be a "list". So adj could also be:
Code:
`int adj[4];`

Using the STL will be less efficient, but possibly "easier" -- it depends which syntax you are interested in learning.

Originally Posted by tabstop
If you're using an adjacency list, then every node in the list represents two square boxes that are connected.
That's a different definition of "adjacency list" than the one here:

6. Originally Posted by MK27
Yes, the list is a list of each node/point in the maze, together with a list of all it's adjacent nodes. So a C struct might look like:
Code:
```typedef struct _point {
char[8] label;
} point;```
Since in a 2D maze a point can have at most 4 adjacent points. If less, set the remaining pointers in the adj array to NULL.

Using the STL will be less efficient, but possibly "easier" -- it depends which syntax you are interested in learning.

That's a different definition of "adjacency list" than the one here:
Adjacency list - Wikipedia, the free encyclopedia
You've got that backwards. The adjacency list is what I have; the incidence list is what you are advocating.

EDIT: I'll quote:
If the graph is undirected, every entry is a set (or multiset) of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node and the other denoting the destination node of the corresponding arc.
some texts, such as that of Goodrich and Tamassia, advocate a more object oriented variant of the adjacency list structure, sometimes called an incidence list, which stores for each vertex a list of objects representing the edges incident to that vertex.

7. Originally Posted by tabstop
If you're using an adjacency list, then every node in the list represents two square boxes that are connected.

How can each node in the list represent two square boxes?

8. Originally Posted by tabstop
You've got that backwards. The adjacency list is what I have; the incidence list is what you are advocating.

EDIT: I'll quote:
No, I'll quote:
In computer science, an adjacency list is a data structure for representing graphs. In an adjacency list representation, we keep, for each vertex in the graph, a list of all other vertices which it has an edge to (that vertex's "adjacency list"). For instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an example of this type of representation. Another example is the representation in Cormen et al. in which an array indexed by vertex numbers points to a singly-linked list of the neighbors of each vertex.
So, either you are wrong or the people responsible for the wiki article just made all this stuff up.

9. Originally Posted by iamnew

How can each node in the list represent two square boxes?
That would just be a list of pairs, one for each edge (not each point). If this is an assignment, I guess you need to resolve the question of how "adjacency list" is defined, tabstop's way (tabstop is no dummy), or the way described in the wikipedia article on it (see above post):

Adjacency list - Wikipedia, the free encyclopedia

I just looked this up today, but the definition there is pretty clear, and it is not a list of edge pairs, so...you do need to resolve that. If you do it one way and the other definition is expected, you'll fail.

10. Originally Posted by iamnew

How can each node in the list represent two square boxes?
Every edge is represented by a pair of "whatever you're calling your boxes" that represent the two ends. You'll need a structure for pairs, or you can use the built-in library std::pair object.

11. Okay so the graph that i have to define should be a undirected one. Am i correct.

12. Originally Posted by MK27
No, I'll quote:

So, either you are wrong or the people responsible for the wiki article just made all this stuff up.
I've only got two references here at home, one of which doesn't mention adjacency lists at all and the other agrees with you (and obviously wiki has both, since we can both quote it). I had thought that the adjacency/incidence list distinction was more common than it apparently is.

13. Originally Posted by iamnew
Okay so the graph that i have to define should be a undirected one. Am i correct.
Undirected would mean you don't care which direction they travel along the edge (i.e. no one-way doors).

14. Originally Posted by tabstop
I've only got two references here at home, one of which doesn't mention adjacency lists at all and the other agrees with you (and obviously wiki has both, since we can both quote it). I had thought that the adjacency/incidence list distinction was more common than it apparently is.
Hmmm. I suppose this kind of hinges on what the list is for, since the two versions would be useful in different ways. If it's the goal of an assignment, then it has no real purpose beyond that. Hopefully iamnew understands what's going on.

Originally Posted by iamnew
Okay so the graph that i have to define should be a undirected one. Am i correct.
Looks that way to me, yes.

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

Page 1 of 3 123 Last