C Directed Graph Implementation Choice

Question

Welcome mon amie,

In some homework of mine, I feel the need to use the Graph ADT. However, I'd like to have it, how do I say, generic. That is to say, I want to store in it whatever I fancy.

The issue I'm facing, has to do with complexity. What data structure should I use to represent the set of nodes? I forgot to say that I already decided to use the Adjacency list technic.

Generally, textbooks mention a linked list, but, it is to my understanding that whenever a linked list is useful and we need to perform searches, a tree is better.

But then again, what we need is to associate a node with its list of adjacent nodes, so what about an hash table?

Can you help me decide in which data structure (linked list, tree, hash table) should i store the nodes?

Answer 1

...the Graph ADT. However, I'd like to have it, how do I say, generic. That is to say, I want to store in it whatever I fancy.

That's basically the point of an ADT (Abstract Data Type).

---

Regarding which data structure to use, you can use either. For the set of nodes, a Hash table would be a good option (if you have a good C implementation for it). You will have amortized O(1) access to any node. A LinkedList will take worst case O(n) time to find a node, a Balanced Tree will be O(logn) and won't give you any advantage over the hash table unless for some reason you will sort the set of nodes a LOT (in which case using an inorder traversal of a tree is sorted and in O(n) time)

Regarding adjacency lists for each node, it depends what you want to do with the graph. If you will implement only, say, DFS and BFS, you need to iterate through all neighbors of a specific node, so LinkedList is the simplest way and it is sufficient.

But, if you need to check if a specific edge exists, it will take you worst case O(n) time because you need to iterate through the whole list (An Adjacency Matrix implementation would make this op O(1))

A LinkedList of adjacent nodes can be sufficient, it depends on what you are going to do.