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!