Breadth First Search

pick a language to open the code

from collections import deque


def breadth_first(start, goal):
    prev = {start: -1}
    queue = deque([start])
    while queue:
        cell = queue.popleft()
        if cell == goal:
            return path_to(prev, goal)
        for other in neighbors(cell):
            if other not in prev:
                prev[other] = cell
                queue.append(other)
    return []

function breadthFirst(start, goal) {
  const prev = new Map([[start, -1]]);
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const cell = queue[head++];
    if (cell === goal) return pathTo(prev, goal);
    for (const other of neighbors(cell)) {
      if (prev.has(other)) continue;
      prev.set(other, cell);
      queue.push(other);
    }
  }
  return [];
}

int breadth_first(int start, int goal, int prev[], int n) {
    int* queue = malloc(sizeof(int) * n);
    int head = 0, tail = 0;
    for (int i = 0; i < n; i++) prev[i] = -2;
    prev[start] = -1;
    queue[tail++] = start;
    while (head < tail) {
        int cell = queue[head++];
        if (cell == goal) { free(queue); return 1; }
        for (int d = 0; d < 4; d++) {
            int other = neighbor(cell, d);
            if (other < 0 || prev[other] != -2) continue;
            prev[other] = cell;
            queue[tail++] = other;
        }
    }
    free(queue);
    return 0;
}

std::vector<int> breadth_first(int start, int goal) {
    std::unordered_map<int, int> prev{{start, -1}};
    std::queue<int> queue;
    queue.push(start);
    while (!queue.empty()) {
        int cell = queue.front();
        queue.pop();
        if (cell == goal) return path_to(prev, goal);
        for (int other : neighbors(cell)) {
            if (prev.count(other) > 0) continue;
            prev[other] = cell;
            queue.push(other);
        }
    }
    return {};
}

static List<int> BreadthFirst(int start, int goal) {
    var prev = new Dictionary<int, int> { [start] = -1 };
    var queue = new Queue<int>();
    queue.Enqueue(start);
    while (queue.Count > 0) {
        int cell = queue.Dequeue();
        if (cell == goal) return PathTo(prev, goal);
        foreach (int other in Neighbors(cell)) {
            if (prev.ContainsKey(other)) continue;
            prev[other] = cell;
            queue.Enqueue(other);
        }
    }
    return new List<int>();
}

static List<Integer> breadthFirst(int start, int goal) {
    Map<Integer, Integer> prev = new HashMap<>();
    prev.put(start, -1);
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(start);
    while (!queue.isEmpty()) {
        int cell = queue.poll();
        if (cell == goal) return pathTo(prev, goal);
        for (int other : neighbors(cell)) {
            if (prev.containsKey(other)) continue;
            prev.put(other, cell);
            queue.add(other);
        }
    }
    return List.of();
}