Logo

Programming-Idioms

# 130 Depth-first traversal in a graph
Call th function f on every vertex accessible from the vertex v, in depth-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 
#include <functional>
#include <stack>
#include <unordered_set>
void dfs(Node& root, std::function<void(Node*)> f) {
  std::stack<Node*> queue;
  queue.push(&root);
  std::unordered_set<const Node*> visited;
  while (!queue.empty()) {
    Node* const node = queue.top();
    queue.pop();
    f(node);
    visited.insert(node);
    for (Node* const neighbor : node->neighbors) {
      if (visited.find(neighbor) == visited.end()) {
        queue.push(neighbor);
      }
    }
  }
}
func (v *Vertex) Dfs(f func(*Vertex), seen map[*Vertex]bool) {
	seen[v] = true
	f(v)
	for next, isEdge := range v.Neighbours {
		if isEdge && !seen[next] {
			next.Dfs(f, seen)
		}
	}
}
func (v *Vertex[L]) Dfs(f func(*Vertex[L]), seen map[*Vertex[L]]bool) {
	seen[v] = true
	f(v)
	for next, isEdge := range v.Neighbours {
		if isEdge && !seen[next] {
			next.Dfs(f, seen)
		}
	}
}
use Tree::Fast qw();
my $iter = $tree->traverse;
while (my $v = $iter->()) {
    f($v);
}
def depth_first(start, f):
  seen = set()
  stack = [start]
  while stack:
    vertex = stack.pop()
    f(vertex)
    seen.add(vertex)
    stack.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 dft_helper(start: Rc<RefCell<Vertex<V>>>, f: &impl Fn(&V), s: &mut Vec<*const Vertex<V>>) {
	s.push(start.as_ptr());
	(f)(&start.borrow().value);
	for n in &start.borrow().neighbours {
		let n = n.upgrade().expect("Invalid neighbor");
		if s.iter().all(|&p| p != n.as_ptr()) {
			Self::dft_helper(n, f, s);
		}
	}
}

Preview