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 <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE 50   // size of symbol table
#define MAX 20    // max length of identifier

// Structure for symbol table entry
typedef struct {
    char name[MAX];
    char type[MAX];
} Symbol;

Symbol table[SIZE];
int count = 0;

// Function to insert symbol
void insert(char *name, char *type) {
    if (count < SIZE) {
        strcpy(table[count].name, name);
        strcpy(table[count].type, type);
        count++;
        printf("Inser
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE 50   // size of symbol table
#define MAX 20    // max length of identifier

// Structure for symbol table entry
typedef struct {
    char name[MAX];
    char type[MAX];
} Symbol;

Symbol table[SIZE];
int count = 0;

// Function to insert symbol
void insert(char *name, char *type) {
    if (count < SIZE) {
        strcpy(table[count].name, name);
        strcpy(table[count].type, type);
        count++;
        printf("Inser
#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