Logo

Programming-Idioms

# 129 Breadth-first traversal in a graph
Call the function f on every vertex accessible from the vertex start, in breadth-first prefix order
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
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)
    seen.add(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 {
	        let n = n.upgrade().expect("Invalid neighbour");
	        if q.iter().all(|v| v.as_ptr() != n.as_ptr()) {
	            q.push(n);
	        }
	    }
	}
}

Preview