Graph traversal

from collections import deque


def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order


def dfs(graph, start):
    seen = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in seen:
                stack.append(nxt)
    return order

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      if (!seen.has(next)) {
        seen.add(next);
        queue.push(next);
      }
    }
  }
  return order;
}

function dfs(graph, start) {
  const seen = new Set();
  const stack = [start];
  const order = [];
  while (stack.length > 0) {
    const node = stack.pop();
    if (seen.has(node)) continue;
    seen.add(node);
    order.push(node);
    for (const next of [...graph[node]].reverse()) {
      if (!seen.has(next)) stack.push(next);
    }
  }
  return order;
}

func bfs(graph [][]int, start int) []int {
	seen := map[int]bool{start: true}
	queue := []int{start}
	order := []int{}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)
		for _, next := range graph[node] {
			if !seen[next] {
				seen[next] = true
				queue = append(queue, next)
			}
		}
	}
	return order
}

func dfs(graph [][]int, start int) []int {
	seen := map[int]bool{}
	stack := []int{start}
	order := []int{}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if seen[node] {
			continue
		}
		seen[node] = true
		order = append(order, node)
		for i := len(graph[node]) - 1; i >= 0; i-- {
			if next := graph[node][i]; !seen[next] {
				stack = append(stack, next)
			}
		}
	}
	return order
}

use std::collections::{HashSet, VecDeque};

fn bfs(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut seen = HashSet::from([start]);
    let mut queue = VecDeque::from([start]);
    let mut order = Vec::new();
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &next in &graph[node] {
            if seen.insert(next) {
                queue.push_back(next);
            }
        }
    }
    order
}

fn dfs(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut seen = HashSet::new();
    let mut stack = vec![start];
    let mut order = Vec::new();
    while let Some(node) = stack.pop() {
        if !seen.insert(node) {
            continue;
        }
        order.push(node);
        for &next in graph[node].iter().rev() {
            if !seen.contains(&next) {
                stack.push(next);
            }
        }
    }
    order
}