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!