# Programming-Idioms

This language bar is your friend. Select your favorite languages!
Select your favorite languages :
• Or search :

# Idiom #130 Depth-first traversing 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)
}
}
}```
`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)
stack.extend(
v for v in vertex.adjacent if v not in seen
)```
```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 {
let n = n.upgrade().expect("Invalid neighbor");
if s.iter().all(|&p| p != n.as_ptr()) {
Self::dft_helper(n, f, s);
}
}
}```

programming-idioms.org