Noobish_Monk's blog

How to store rooted trees efficiently?
By Noobish_Monk, history, 16 months ago, In English

Hello. I've heard there is a way to store trees using like 3 integer arrays. How exactly is it done? And can it be extended on any graph?

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +18 Vote: I do not like it

What do expect such a storage to provide ? If you just want to encode a rooted tree I am pretty sure storing the parent of every node other than the root is the most efficient way.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I meant storing the tree so it's possible to do dfs on it

    → Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

I came up with this approach for a tree. We can have 3 arrays. The first array will be about storing the indegree. So initially we will store the indegree of every node. Now we will calculate the prefix sum of this array. Once we have calculated the prefix sum, we will know for every node, how many other vertices it is connected to. Also we can use this array for filling another array with its connected nodes. For example if the indegree of a node is $$$3$$$ and its prefix sum is $$$15$$$ , this means its connected edges will be stored at positions $$$15,14,13$$$ in the second array. Now about the third array we will use it for efficiently filling the second array.

A sample implementation

→ Reply
»
16 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Probably what you’ve heard was representing graphs using (statically allocated) linked lists. You need 3 arrays:

  • $$$vertex[i]$$$ is the neighbouring vertex $$$v_i$$$ of directed arc $$$e_i = (u_i, v_i)$$$ ($$$O(M)$$$ size)
  • $$$nxt[i]$$$ is the next arc after $$$e_i = (u_i, v_i)$$$ in the adjacency list of $$$u_i$$$ ($$$O(M)$$$ size)
  • $$$head[i]$$$ is the index of the first arc in the adjacency list of $$$i$$$ ($$$O(N)$$$ size)

To ‘add’ an arc $$$(u_i, v_i)$$$ you do sth like: 

vertex[i] = v_i
nxt[i] = head[u_i]
head[u_i] = i
→ Reply