Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Блог пользователя Inversentropir-36

Is it better to open the memory pool or a vector to save a graph?
Автор Inversentropir-36, история, 5 лет назад, По-английски

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++;  
}
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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)

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить