Hi,I am beginner and I want to know what is the fastest way to implementing graphs in C++ for some algorithms of graph(DFS,BFS,.....). Sorry for my poor english.

# | User | Rating |
---|---|---|

1 | tourist | 3581 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Petr | 3161 |

4 | LHiC | 3158 |

5 | CongLingDanPaiSh…5 | 3116 |

6 | ko_osaga | 3115 |

7 | mnbvmar | 3111 |

8 | Um_nik | 3104 |

9 | Benq | 3098 |

10 | Swistakk | 3089 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | Errichto | 163 |

3 | rng_58 | 161 |

4 | tourist | 158 |

5 | Vovuh | 150 |

5 | Um_nik | 150 |

7 | Swistakk | 149 |

7 | Petr | 149 |

9 | PikMike | 148 |

10 | 300iq | 147 |

Hi,I am beginner and I want to know what is the fastest way to implementing graphs in C++ for some algorithms of graph(DFS,BFS,.....). Sorry for my poor english.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2018 14:18:10 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I can help you that, using lists!

Thing is you'll get the edges like "there's an edge from node x to node y of cost z". For each edge i, you'll "put" it your graph:

cost[i]=z;

node[i]=y;

next[i]=last[x];

last[x]=i;

At any time, last[x] will remember which is the last edge that goes from node x to another node. When you want to see the neighbors of a node, watch this:

p=last[x];

while(p!=0){

//node[p] is my neighbor

//the cost of the edge between me and node[p] is cost[p]

p=next[p];

}

This works really fast, and it's quite easy after you get it. So you'll need next[EDGES], node[EDGES] and, if the problem specifies, cost[EDGES]. Of course last[NODES]. Remember that in a undirected graph you'll need 2 edges for each step: one that goes form x to y, and one that goes from y to x, and you'll have double number of edges. Got it?

tnx for you help.

thanks

Use adjacency list representation. U can use vector to easily maintain your adjacency list. For example lest's assume a graph with n nodes and m edges, the edges are given in the form (a b) where there is a directed edge from a to b. U can do the following

traversing the adjacency list of any node is easy;

For sparse graphs you can use static arrays to index the edges:

For me, the easiest and shortest way is to use a vector and range for loops from C++11.

Declaration of adjacency list:Add directed edgeu->v:Process edges of nodev:Of course, if edges also have a weight/capacity associated with them, you'd declare a

`pair<int,int>`

vector instead.I hope I've been of help.

we're just declaring an vector of ints and not vector of vector of ints.

for example, this makes sense vector< vector > gr; but I can see your method works as well.

can you explain how this works ? thanks.

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge. Adjacency lists use memory in proportion to the number edges.

So... I usually use:

Graph with no weights`vector<vector<int> > graph;`

Graph with weights`vector<vector<pair<int,int> > > graph;`

:P

Btw, I think you gonna love this blog... :]

I think for adjacency linklist :

for weighted graph :

`vector<pair<int,int> > Graph[number_of_vertex];`

for unweighted graph :

`vector Graph[number_of_vertex];`

for adjacency matrix :

for weighted and unweighted : use 2D array

`int Graph[number_of_vertex][number_of_vertex];`