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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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?
Название |
---|
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.
I meant storing the tree so it's possible to do dfs on 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
Probably what you’ve heard was representing graphs using (statically allocated) linked lists. You need 3 arrays:
To ‘add’ an arc $$$(u_i, v_i)$$$ you do sth like:
I guess that's it. Thanks