Logo

Programming-Idioms

History of Idiom 130 > diff from v8 to v9

Edit summary for version 9 by dan:
New Cpp implementation by user [dan]
↷

Version 8

2019-01-05, 11:46:15

Version 9

2019-09-27, 17:26:18

Idiom #130 Depth-first traversing in a graph

Call a function f on every vertex accessible for vertex v, in depth-first prefix order

Illustration

Idiom #130 Depth-first traversing in a graph

Call a function f on every vertex accessible for vertex v, in depth-first prefix order

Illustration
Extra Keywords
dfs
Extra Keywords
dfs
Imports 
#include <functional>
#include <stack>
#include <unordered_set>
Code 
void dfs(Node& root, std::function<void(Node*)> f) {
  std::stack<Node*> queue;
  queue.push(&root);
  std::unordered_set<const Node*> visited;
  while (!queue.empty()) {
    Node* const node = queue.top();
    queue.pop();
    f(node);
    visited.insert(node);
    for (Node* const neighbor : node->neighbors) {
      if (visited.find(neighbor) == visited.end()) {
        queue.push(neighbor);
      }
    }
  }
}