News for hackers. Stuff that matters.
Re:Big-O Algorithm Complexity Cheat Sheet by ufo on Saturday May 04, 2013 @08:43PM (#5656944)
Storing the graph structure in a BST is only useful if your graph is very sparse and you need to have fast lookup for checking specific edges (say, given two nodes, find the cost for the edge between them).

If your graph is dense, using a an adjacency matrix is simpler and will be faster most of the time. If you don't need to query specifific edges and all you need to do is iterate over the edges for given vertices than using adgacency lists (or vectors) is simpler and does the job just as well.

Re:Big-O Algorithm Complexity Cheat Sheet by fmax30 on Sunday May 05, 2013 @12:22AM (#5657442)
if my graph is dense then would using a adjacency matrix take like O(V^2) space complexity ? Anyway I was just suggesting this because I use it in practice. Just wanted to know the cons of it if any.
Re:Big-O Algorithm Complexity Cheat Sheet by gsg on Sunday May 05, 2013 @04:29AM (#5657840)
The space taken by an adjacency matrix doesn't depend on edge count. That's why it is usually the favoured representation for dense graphs.
Re:Big-O Algorithm Complexity Cheat Sheet by ufo on Sunday May 05, 2013 @01:30PM (#5659054)
Dense graphs, by definition, have close to O(V²) edges already so adjacency matrices aren't wasting space in that case.