Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### fafal_abnir's blog

By fafal_abnir, 4 years ago, ,

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.

•
• +1
•

 » 4 years ago, # |   0 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?
•  » » 4 years ago, # ^ |   0 tnx for you help.
•  » » 3 months ago, # ^ |   0 thanks
 » 4 years ago, # | ← Rev. 2 →   0 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 vector< vector > gr; cin>>n>>m; gr.clear(); gr.resize(n+1); while(m--) { cin>>a>>b; gr[a].push_back(b); } traversing the adjacency list of any node is easy; for(int i=0,i
 » 4 years ago, # |   0 For sparse graphs you can use static arrays to index the edges: Every node remembers the index of the last edge out of it, Every edge remembers the previous edge (-1 if none), Every edge remembers the destination node. const int N = ..; /* nodes */ const int M = ..; /* edges */ int id = 0; /* next edge id */ int last[N], prev[M], to[M]; /* graph */ /* init */ memset(last, -1, sizeof(last)); /* add directed edge (x, y) */ void add(int x, int y) { prev[id] = last[x]; last[x] = id; to[id] = y; id += 1; } /* iterate over adjacent nodes of x */ for(int e = last[x]; e != -1; e = prev[e]) { int y = to[e]; /* process edge (x, y) */ } 
 » 4 years ago, # |   0 For me, the easiest and shortest way is to use a vector and range for loops from C++11.Declaration of adjacency list: vector E[MAX_NODES]; Add directed edge u->v: E[u].push_back(v); Process edges of node v: for(int u : E[v]) { ... } Of course, if edges also have a weight/capacity associated with them, you'd declare a pair vector instead.I hope I've been of help.
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # | ← Rev. 2 →   0 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 weightsvector > graph;Graph with weightsvector > > graph; :P
•  » » 2 years ago, # ^ |   0 Btw, I think you gonna love this blog... :]
 » 2 years ago, # |   0 I think for adjacency linklist :for weighted graph :  vector > 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];