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, In English,

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.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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<int> > 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<gr[node].size();i++)
{
  int adjacent_node=gr[node][i];
 // do ur calculation
}
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

Declaration of adjacency list:

vector<int> 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<int,int> vector instead.

I hope I've been of help.

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

    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   Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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];