Inversentropir-36's blog

Is it better to open the memory pool or a vector to save a graph?
By Inversentropir-36, history, 5 years ago, In English

Just like title, Is it better to open the memory pool or a vector to save a graph?

I personally like using Vector to save a graph...

I just learned graph theory, so I don't know how to use it. :(

memory pool:

struct Edge{
    int next;
    int to;
    int w;
};
void add(int u,int v,int w)  {  
    edge[cnt].w = w;  
    edge[cnt].to = v;  
    edge[cnt].next = head[u];  
    head[u] = cnt++;  
}
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I think the "memory pool“ (probably should be called linked list?) method should mainly be used for network flow (when you need to quickly access an edge's reverse edge) and when performance and constant factors are critical.

The "memory pool" method is probably faster than vector, since vector dynamically allocates memory for its data which incurs overhead. However, it is easier to use a vector, since you can directly iterate over all of its contents with a for-each loop (for(auto& v:elist[u]) and the like)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I think use vector is easy to use, But now, I want to try linked list XD

    And thank you!

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Assume vertices are 1..n. I like to use

// adj[i] := The set of vertices that can be reached from i via a single edge.
vector<vector<int>> adj(n + 1);

// visited[i] := Has i been visited yet by the graph traversal (BFS, DFS, etc.)
vector<bool> visited(n + 1, false);

Its inspired by https://cses.fi/book/book.pdf which is where I learned (am still learning) graphs.

→ Reply