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

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

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
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 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?

»
9 лет назад, # |
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<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
}
»
9 лет назад, # |
  Проголосовать: нравится 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) */
}
»
9 лет назад, # |
  Проголосовать: нравится 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<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.

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

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