dfs

Posted on | In | Comments: 
1
2
3
4
5
6
struct GraphNode {
  int val;
  vector<GraphNode *> neighbors;
};

unordered_set<GraphNode *> visited;

Recursive DFS

1
2
3
4
5
6
7
8
9
void dfs(GraphNode &nd) {
  printf("%d", nd.val);
  visited.insert(&nd);

  for (auto next : nd.neighbors)
    if (!visited.count(next)) {
      dfs(*next);
    }
}

Non-recursive DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void no_recursive_dfs(GraphNode &start) {
  stack<GraphNode *> s;
  s.push(&start);

  while (!s.empty()) {
    auto cur = s.top();
    s.pop();
    printf("%d\n", cur->val);

    for (auto next : cur->neighbors) {
      if (!visited.count(next)) {
        s.push(next);
        visited.insert(next);
      }
    }
  }
}