Graph -adjacency linked list

hi i want to implement graph using adjacency linked list cos adjacency matrix consumes o(n^2)....

any help or suggestions on how to implement adjacency linked list using c++ stl

thanks

It depends on how you want to do it. For example, you could use a std::map to map the nodes to a std::list (a doubly linked list) of pointers or iterators to adjacent nodes.

thanks.....can i have an example .....implementation using nodes and list using stl's

Wouldn't using a std::multi_map be easiest?
An adjacency matrix should give better performance though. The graph would have to be pretty large, and sparsely connected, for me to want to use a multi_map instead.

Quote:

---

Originally Posted by iMalc

Wouldn't using a std::multi_map be easiest?

---

Possibly, though it is std::multimap.

Quote:

---

Originally Posted by iMalc

Wouldn't using a std::multi_map be easiest?

---

Depending on how multimap is implemented, mightn't using a multimap defeat much of the efficiency that an adjacency list implementation should provide?

Wouldn't it be simpler and more efficient to represent the graph as a (probably sorted) std::list of nodes, with each node having (in addition to "value", "color", etc.) a std::vector of pointers to its neighbors? I'm suggesting vector since "in general" the adjacency lists don't have to be sorted. But if the application requires searching the adjacency lists for specific entries, each node can have a sorted std::list of neighbor pointers.

Quote:

---

Originally Posted by R.Stiltskin

Depending on how multimap is implemented, mightn't using a multimap defeat much of the efficiency that an adjacency list implementation should provide?

Wouldn't it be simpler and more efficient to represent the graph as a (probably sorted) std::list of nodes, with each node having (in addition to "value", "color", etc.) a std::vector of pointers to its neighbors? I'm suggesting vector since "in general" the adjacency lists don't have to be sorted. But if the application requires searching the adjacency lists for specific entries, each node can have a sorted std::list of neighbor pointers.

---

Oops yeah no underscore, my blunder.

I don't think an adjacency list provides much efficiency. Seeing if two nodes are neighbours is an O(n*m) operation where n = the number of items in the list, and m = the number of items in the vector. Compare that to the O(1) of an adjacency matrix and that's just pitiful.
If you don't specifically need to access items in a std::list in sorted order, then there isn't any point in sorting it. It's not like sorting it would allow you to perform a binary search on it anyway.

Depending on how often you need to connect, disconnect, add, or remove nodes, the fastest solution (outside of a matrix) is probably to use a vector of pairs with std::lower_bound / std::upper_bound / std::equal_range. That way once you've built it, queries can be done in O(log n) time, and in contiguous memory so its fast and has no per-item overhead.

Seriously, an adjacency matrix is still a great idea even for a moderate-sized matrix though. You can pack each connection into 1 bit meaning that a 64 node graph's adjacency information could be stored in just 64 bytes. (64 bits * 64 bits = 512 bits = 64 bytes)

Plz tell me a good website to learn about graphs in C++ completely.