Breadth-First and Depth-First Search in Python, Java and TypeScript

from collections import deque

Graph = dict[str, list[str]]


def build_graph(edges: list[tuple[str, str]]) -> Graph:
    graph: Graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)
    for neighbours in graph.values():
        neighbours.sort()
    return graph


def breadth_first(graph: Graph, start: str) -> list[str]:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
    return order


def depth_first(graph: Graph, start: str) -> list[str]:
    order: list[str] = []
    visited: set[str] = set()

    def visit(vertex: str) -> None:
        visited.add(vertex)
        order.append(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visit(neighbour)

    visit(start)
    return order


edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"), ("D", "F"), ("E", "F")]
graph = build_graph(edges)
print("breadth-first from A:", " ".join(breadth_first(graph, "A")))
print("depth-first from A:", " ".join(depth_first(graph, "A")))

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class TraversalCode {
    static Map<String, List<String>> buildGraph(String[][] edges) {
        Map<String, List<String>> graph = new TreeMap<>();
        for (String[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }
        graph.values().forEach(neighbours -> neighbours.sort(null));
        return graph;
    }

    static List<String> breadthFirst(Map<String, List<String>> graph, String start) {
        Set<String> visited = new HashSet<>(List.of(start));
        ArrayDeque<String> queue = new ArrayDeque<>(List.of(start));
        List<String> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            order.add(vertex);
            for (String neighbour : graph.get(vertex)) {
                if (visited.add(neighbour)) {
                    queue.add(neighbour);
                }
            }
        }
        return order;
    }

    static void visit(Map<String, List<String>> graph, String vertex, Set<String> visited, List<String> order) {
        visited.add(vertex);
        order.add(vertex);
        for (String neighbour : graph.get(vertex)) {
            if (!visited.contains(neighbour)) {
                visit(graph, neighbour, visited, order);
            }
        }
    }

    static List<String> depthFirst(Map<String, List<String>> graph, String start) {
        List<String> order = new ArrayList<>();
        visit(graph, start, new HashSet<>(), order);
        return order;
    }

    public static void main(String[] args) {
        String[][] edges = {{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}, {"C", "E"}, {"D", "F"}, {"E", "F"}};
        Map<String, List<String>> graph = buildGraph(edges);
        System.out.println("breadth-first from A: " + String.join(" ", breadthFirst(graph, "A")));
        System.out.println("depth-first from A: " + String.join(" ", depthFirst(graph, "A")));
    }
}

type Graph = Map<string, string[]>;

function buildGraph(edges: [string, string][]): Graph {
  const graph: Graph = new Map();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u)!.push(v);
    graph.get(v)!.push(u);
  }
  for (const neighbours of graph.values()) neighbours.sort();
  return graph;
}

function breadthFirst(graph: Graph, start: string): string[] {
  const visited = new Set([start]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const vertex = queue[head++];
    for (const neighbour of graph.get(vertex)!) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour);
        queue.push(neighbour);
      }
    }
  }
  return queue;
}

function depthFirst(graph: Graph, start: string): string[] {
  const visited = new Set<string>();
  const order: string[] = [];
  const visit = (vertex: string): void => {
    visited.add(vertex);
    order.push(vertex);
    for (const neighbour of graph.get(vertex)!) {
      if (!visited.has(neighbour)) visit(neighbour);
    }
  };
  visit(start);
  return order;
}

const edges: [string, string][] = [["A", "B"], ["A", "C"], ["B", "D"], ["C", "D"], ["C", "E"], ["D", "F"], ["E", "F"]];
const graph = buildGraph(edges);
console.log(`breadth-first from A: ${breadthFirst(graph, "A").join(" ")}`);
console.log(`depth-first from A: ${depthFirst(graph, "A").join(" ")}`);