• Or search :

# Idiom #129 Breadth-first traversing in a graph

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

```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)
q.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 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 {