# Idiom #129 Breadth-first traversal in a graph

Call the function f on every vertex accessible from the vertex start, in breadth-first prefix order

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

// ...

fn bft(start: Rc<RefCell<Vertex<V>>>, f: impl Fn(&V)) {
let mut q = vec![start];
let mut i = 0;
while i < q.len() {
let v = Rc::clone(&q[i]);
i += 1;
(f)(&v.borrow().value);
for n in &v.borrow().neighbours {
if q.iter().all(|v| v.as_ptr() != n.as_ptr()) {
q.push(n);
}
}
}
}``````
``````func (start *Vertex) Bfs(f func(*Vertex)) {
queue := []*Vertex{start}
seen := map[*Vertex]bool{start: true}
for len(queue) > 0 {
v := queue[0]
queue = queue[1:]
f(v)
for next, isEdge := range v.Neighbours {
if isEdge && !seen[next] {
queue = append(queue, next)
seen[next] = true
}
}
}
}``````
``use Tree::Fast qw();``
``````my \$iter = \$tree->traverse(\$tree->LEVEL_ORDER);
while (my \$v = \$iter->()) {
f(\$v);
}``````
``from collections import deque``
``````def breadth_first(start, f):
seen = set()
q = deque([start])
while q:
vertex = q.popleft()
f(vertex)