Logo

Programming-Idioms

  • Go
  • Clojure

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

A graph having 5 vertices and 6 edges 
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
			}
		}
	}
}

Bfs is a method of type *Vertex : the receiver is the start node.
The function f is a parameter of the traversal method.
use Tree::Fast qw();
my $iter = $tree->traverse($tree->LEVEL_ORDER);
while (my $v = $iter->()) {
    f($v);
}
New implementation...
< > ⌨
programming-idioms.org 
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
			}
		}
	}
}
my $iter = $tree->traverse($tree->LEVEL_ORDER);
while (my $v = $iter->()) {
    f($v);
}
def breadth_first(start, f):
  seen = set()
  q = deque([start])
  while q:
    vertex = q.popleft()
    f(vertex)
    seen.add(vertex)
    q.extend(v for v in vertex.adjacent if v not in seen)
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 {
	        let n = n.upgrade().expect("Invalid neighbour");
	        if q.iter().all(|v| v.as_ptr() != n.as_ptr()) {
	            q.push(n);
	        }
	    }
	}
}