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

Автор zscoder, 11 лет назад, По-английски

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

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

»
11 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
vector<vector<int>> G;
  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится
vector<int> G[N];	// where N is the number of nodes
»
11 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How about in java? What should I use then?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    ArrayList <Integer>[] adjacencyList = new ArrayList[N];  //N -> number of vertices
    
»
11 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

[trollface mode]

set< pair< T, T > > G;

[/trollface mode]

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

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

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, quite a good structure for Bellman–Ford algorithm

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

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];
}
»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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!