2

Is it possible to make an array of arrays in C? More specifically, is it possible to make a list (array) of adjacency lists (arrays)?

And if so, how?

My textbook uses a list of adjacency lists for Dijkstra's algorithm (and in a lot of other algorithms) instead of using an adjacency matrix, though the book is in pseudocode and even then it makes no reference whatsoever on how to implement the list...

Supposedly, list of adjacency lists are more efficient in a lot of algorithms than adjacency matrices. I thought of using linked lists, but AFAIK it would be the same as using an adjacency matrix, so it would make no point at all to implement it this way...

Improve this question
3
  • 3
    It's software: you can make anything you want. Commented Mar 9, 2013 at 7:09
  • This link may help you. stackoverflow.com/questions/3732856/arraylist-in-c Commented Mar 9, 2013 at 7:11
  • Isn't char **argv what you are trying to build yourself? Commented Mar 9, 2013 at 9:08

3 Answers 3

Reset to default
5

Did you mean a multidimensional array?

int mdarr[10][20];
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

No, this is what we call a matrix. In my book, the function "dijkstra" gets an unidimensional array as an argument, "Adj[]", which is a list of adjacency lists. This is how they manipulate it, in pseudocode: "int u = [some_number]; int v; for each v in Adj[u] do ..."
Where Adj[u] is supposed to be the adjacency list of the vertex 'u', and the integers 'v' are the elements of this list. I'm clueless on how to do that in C.
@CarpeNoctem I don't see your problem. Are you asking about how to implement a particular data structure? Or what?
I'm asking about how to implement an array, where each element of the array is an adjacency list. The book doesn't says anything about making a new struct: We were taught how to make adjacency lists in arrays, but it didn't explain how to make an ~array~, were each element is one of these lists, and that's where I'm asking for help.
Seriously, thats ^ what he wanted -_-
|
3

Is it possible to make an array of arrays in C?

Yes.

More specifically, is it possible to make a list (array) of adjacency lists (arrays)?

Yes, it can be implemented using a linked list (or array in your case) of linked lists.

And if so, how?

One list (or array) could maintain nodes, each of which will point to the actual adjacency list as well as contain information about the current point of the graph. This can be implemented creating a struct with the relevant data (one information field and one next pointer, and one pointer to adjacency list)

The second list will be the actual adjacency list of each node. It will be pointed to by the corresponding nodes of the first list. It will contain nodes, each of which will be a graph point connected to the corresponding point in the initial list. It can be implemented similarly, by creating a struct having the relevant data (one field for the next pointer, and one information field).

This is not a multi-dimensional array but is completely different. This will use less space than an adjacency matrix, if your graph is sparse.

As an example, lets take A, B, C, D to be the nodes of an undirected graph such that A is connected to B and C.

Then the lists will be like this :

A -> B -> C -> D
|    |    |
B    A    A
|
C
Improve this answer

Comments

0

Did you mean a three-dimensional array?.

Yo define an adjacency matrix like this aMat[3][3] (graph of three elements).

So, you could define, for example 4 graphs of three elements each like this: aMatMulti[4][3][3].

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.