# 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

``````use std::rc::{Rc, Weak};
use std::cell::RefCell;``````
``````struct Vertex<V> {
value: V,
neighbours: Vec<Weak<RefCell<Vertex<V>>>>,
}

// ...

fn dft_helper(start: Rc<RefCell<Vertex<V>>>, f: &impl Fn(&V), s: &mut Vec<*const Vertex<V>>) {
s.push(start.as_ptr());
(f)(&start.borrow().value);
for n in &start.borrow().neighbours {
if s.iter().all(|&p| p != n.as_ptr()) {
Self::dft_helper(n, f, s);
}
}
}``````
``````#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)
}
}
}``````
``````func (v *Vertex[L]) Dfs(f func(*Vertex[L]), seen map[*Vertex[L]]bool) {
seen[v] = true
f(v)
for next, isEdge := range v.Neighbours {
if isEdge && !seen[next] {
next.Dfs(f, seen)
}
}
}``````
``use Tree::Fast qw();``
``````my \$iter = \$tree->traverse;
while (my \$v = \$iter->()) {
f(\$v);
}``````
``````def depth_first(start, f):
seen = set()
stack = [start]
while stack:
vertex = stack.pop()
f(vertex)