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
This is a discussion on Graph -adjacency linked list within the C++ Programming forums, part of the General Programming Boards category; hi i want to implement graph using adjacency linked list cos adjacency matrix consumes o(n^2).... any help or suggestions on ...
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Possibly, though it is std::multimap.Originally Posted by iMalc
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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)
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Plz tell me a good website to learn about graphs in C++ completely.