simp1eton's blog

By simp1eton, 7 years ago, In English

Hi all,

May I know if anyone knows an efficient way to write iterative dfs? I am asking this because I am writing a program that has to deal with extremely large rooted trees. Even if I increase the stack limit, I think recursive dfs will be much slower than iterative dfs in this case due to the numerous function calls. Therefore, I implemented an iterative dfs as follows.

Note: the tree is rooted tree (edges point from parent to child), so I do not check if vertices have been visited.

vector <int> graph[MAXN];
stack <pair<int,int> > S;

S.push(pair<int,int>(TREE_ROOT,-1));

while(!S.empty()) {
  pair<int,int> cur = S.top();
  S.pop();
  cur.second++;
  // do stuff
  if (cur.second < graph[cur.first].size()) {
    S.push(cur);
    S.push(pair<int,int>(graph[cur.first][cur.second],-1));
  }
  else {
    //do more stuff
  }
}

I am not sure if this is the best way to implement what I have. In practice my performance is not that good. Does anyone have a better implementation? My main concern is with speed.

Thank you!

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why you didn't check that a node is already in the stack or not before push it to stack ?

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Optimize it more by change the stack type become stack of current node only. If you pop the current stack top element must be parent

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

I'm no user of C++, nor am I sure of the correctness of the following code (or even if it's efficient), but I think this is pretty much equivalent to your code and it should also cover an additional common case (just after we've processed a child). This code could be plain shit, but at least it's different. =D

vector <int> graph[MAXN];
int S[2*MAXN], vis[MAXN];

memset(vis, -1, MAXN*sizeof(int));
S[0] = TREE_ROOT;

for(int top = 1; top; )
{
  int v = S[--top];
  if(++vis[v]==0)
    for(int i = 0; i<graph[v].size(); i++)
      S[top++] = v, S[top++] = graph[v][i];
  if(vis[v]>=0) //do stuff (before processing child at S[top-1] if any)
  if(vis[v]>0) //do stuff (after child at S[top+1] been processed)
  if(vis[v]==graph[v].size()) //do more stuff (when all children been processed)
}