This language bar is your friend. Select your favorite languages!

Idiom #129 Breadth-first traversing in a graph

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

Illustration
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
			}
		}
	}
}
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);
	        }
	    }
	}
}
Do you know the best way to do this in your language ?
New implementation...

Idiom created by

programming-idioms.org

Related idioms

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
			}
		}
	}
}
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);
	        }
	    }
	}
}