title: Sparse Graph Implementation & Performance in C++
body: <p>I'm currently working on a directed graph data structure in C++ (no Boost GL for this project). The primary application will be identifying connected components and sinks. The graphs are expected to be sparse (E ~ 4V upper limit on num edges) and will all be uniform weight. I'm trying to decide between adjacency list, incidence list or possibly some other representation that I haven't heard of yet (adj. matrix not an option bc of sparsity). The bottleneck is likely going to be space overall and speed of graph initialization: Graphs will be initialized from potentially huge arrays such that each element in the array will end up being a vertex with a directed edge to one of its neighboring elements. To get the edges for each vertex, all its neighboring elements must be compared first. </p>
  
  <p>My questions are: (1) Which representation is typically faster to initialize and also fast for BFS traversal, (2) What algorithms (other than vanilla BFS) are there for finding connected components? I know it's O(V+E) using BFS (which is optimal, I think) but I'm worried about the size of the intermediate queue as the graph width grows exponentially with height.</p>
  
  <p>Don't have too much experience with graph implementations, so I'd be grateful for any suggestions.</p>