Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • C++

Idiom #130 Depth-first traversal in a graph

Call th function f on every vertex accessible from the vertex v, in depth-first prefix order

#include <functional>
#include <stack>
#include <unordered_set>
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);
      }
    }
  }
}
func (v *Vertex) Dfs(f func(*Vertex), seen map[*Vertex]bool) {
	seen[v] = true
	f(v)
	for next, isEdge := range v.Neighbours {
		if isEdge && !seen[next] {
			next.Dfs(f, seen)
		}
	}
}

Dfs is a method of type *Vertex : the receiver is the start node.
The function f is a parameter of the traversal method.
Start with an empty map as initial seen parameter.

New implementation...