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

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

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

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

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится
vector<vector<int>> G;
  • »
    »
    12 лет назад, скрыть # ^ |
    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);.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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.

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

How about in java? What should I use then?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

[trollface mode]

set< pair< T, T > > G;

[/trollface mode]

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

»
12 лет назад, скрыть # |
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!