Блог пользователя fofao_funk

Way of Storing Edges
Автор fofao_funk, история, 8 лет назад, По-английски

Hi all.

I've came across this way of storing edges in many codes:

void addEdge(int u, int v) {
    head[edges] = v;
    prev[edges] = last[u];
    last[u] = edges++;
}

How does it work? Why is it used over the 'traditional' array of vectors?

I appreciate your help!

  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

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

Its basically the same. It's used because the array of vectors is slower. Personally I have never used it because I find it "ugly" and have never had problem with TL because of graph representation.

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

Good day to you.

You basically have array of edges, where each edge has "pointer" to parent (i.e. previous edge FROM same node) {you might also want TARGET {head in your code} node + PRICE + anything else you want}. You also have to keep (last array) an array with a "pointer" to "TOP" edge from each node.

So basically when you want to iterate over all edges FROM a node, you take look to the "LAST" array and keep iterating over the "pointers" {PREV in your code}.

It might be harder to understand + to operate with. Yet, it is slightly faster + it can be used in languages with no "vector"-like structure .

The memory cost is O(N+M) with no other overhead, which is also nice.

Good Luck!

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

Well, this way of has its pros and cons... I prefer to use it only when solving flow problems. For example, you may want to find quickly the edge, which goes in the opposite direction. If you add edges in pairs, the opposite of E is E^1.

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

Could you please give a link to a full solution with this representation ?

→ Ответить