How can i represent this maze using a adjacency list.
Please help.
How can i represent this maze using a adjacency list.
Please help.
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
Here the strings would be labels for the points (eg. "1,3")Code:map<string,vector<string> >
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
in the adjacency list representation do i have to have nodes for each square box?
If you're using an adjacency list, then every node in the list represents two square boxes that are connected.
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:
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:typedef struct _point { char[8] label; struct _point *adj[4]; } point;
in order for it to be a "list". So adj could also be:Code:point[48];
instead of a pointer array.Code:int adj[4];
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:
http://en.wikipedia.org/wiki/Adjacency_list
Last edited by MK27; 04-28-2010 at 07:26 AM.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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.
No, I'll quote:
So, either you are wrong or the people responsible for the wiki article just made all this stuff up.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.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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.
Last edited by MK27; 04-28-2010 at 07:39 AM.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
Okay so the graph that i have to define should be a undirected one. Am i correct.
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.
Looks that way to me, yes.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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.