News for hackers. Stuff that matters.
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.