# Represent Maze

Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last
• 04-28-2010
iamnew
Represent Maze
How can i represent this maze using a adjacency list.

• 04-28-2010
MK27
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")
• 04-28-2010
iamnew
in the adjacency list representation do i have to have nodes for each square box?
• 04-28-2010
tabstop
If you're using an adjacency list, then every node in the list represents two square boxes that are connected.
• 04-28-2010
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;     struct _point *adj[4]; } 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.

Quote:

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:
• 04-28-2010
tabstop
Quote:

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;     struct _point *adj[4]; } 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:
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.
Quote:

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.
• 04-28-2010
iamnew
Quote:

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?
• 04-28-2010
MK27
Quote:

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:
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.
• 04-28-2010
MK27
Quote:

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.
• 04-28-2010
tabstop
Quote:

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.
• 04-28-2010
iamnew
Okay so the graph that i have to define should be a undirected one. Am i correct.
• 04-28-2010
tabstop
Quote:

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.
• 04-28-2010
tabstop
Quote:

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).
• 04-28-2010
MK27
Quote:

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.

Quote:

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.
• 04-28-2010
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.
Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last