zscoder's blog

Which is the best data structure to implement a graph on?
By zscoder, 10 years ago, In English

Which is the best data structure to implement a graph on?

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it 
vector<vector<int>> G;
→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    This should be upvoted more. It can be cleared more easily than a C-style array using G.clear(); G.resize(N);.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +35 Vote: I do not like it 
vector<int> G[N];	// where N is the number of nodes
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    At least since C++11, one should always consider using std::array instead of a C-style array. Or std::vector, but that has slightly different semantics obviously.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -54 Vote: I do not like it

    .

    → Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How about in java? What should I use then?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it 
    ArrayList <Integer>[] adjacencyList = new ArrayList[N];  //N -> number of vertices
    → Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

[trollface mode]

set< pair< T, T > > G;

[/trollface mode]

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Using two binary searches to access all edges of vertex is the choice of champion.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Actually only one, at least if you plan to iterate over them

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I think, if we want to use two binary searches, we should use something like

      map<int,map<int,int>> G;

      Well, also we can get adjacency matrix and adjacency lists simultaneously in this way :D

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, quite a good structure for Bellman–Ford algorithm

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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:

void add_edge(int x, int y) {
    len++;
    nx[len] = st[x];
    to[len] = y;

    st[x] = len;
}

And to get all nodes from x:

int v = st[x];
while (v) {
    printf("%d ", to[v]);
    v = nx[v];
}
→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply