Which is the best data structure to implement a graph on?
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
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 |
Which is the best data structure to implement a graph on?
Name |
---|
This should be upvoted more. It can be cleared more easily than a C-style array using
G.clear(); G.resize(N);
.Exactly, this should be upvoted more, in my opinion this is more convenient than vector G[N]; — sometimes you want to pass graph to the function or something and I always avoid passing arrays, when I can pass vector. Although in average problems advantages are not that big and it demands additional line G.resize(N); or something, so I'm used to declare it as an array.
At least since C++11, one should always consider using
std::array
instead of a C-style array. Orstd::vector
, but that has slightly different semantics obviously..
How about in java? What should I use then?
[trollface mode]
[/trollface mode]
Using two binary searches to access all edges of vertex is the choice of champion.
Actually only one, at least if you plan to iterate over them
I think, if we want to use two binary searches, we should use something like
Well, also we can get adjacency matrix and adjacency lists simultaneously in this way :D
Well, quite a good structure for Bellman–Ford algorithm
If you don't want to use vectors, you can write use just 3 arrays. Memory is O(2 * M + N).
To add edge, you can write like that:
And to get all nodes from x:
I'd say it may depend on what tasks you are going to solve on this graph, and how the graph is specified, do you need to handle duplicated edges etc.
For edges and vertices you usually use array of lists, 2d array, list of maps, maps of maps etc.
But sometimes you will want some tricky additional structure like enhanced priority queue (for Dijkstra) or disjoint set (for Cruscal?) etc, depending on algorithm.
So your question is just too vague.
The data structure depends directly on what you want to do with the graph. Sometimes you only need the edges (Bellman-Ford, for example), sometimes a matrix (all pairs sp), an UFSet (MST, keep track of graph connectivity if edges are added), an adjacency list (usually best choice for traversal-related problems)...
Do a lot of graph problems and you will see what kinds of representation exists and how to use them!