Exercise: Breadth First Search Shortest Reach

bfs.js

function bfs(n, m, edges, s) {
    // Create adjacency list for the graph
    const adjList = new Array(n + 1).fill().map(() => []);
    // Build the graph from edges
    for (const [u, v] of edges) {
        adjList[u].push(v);
        adjList[v].push(u); // Undirected graph
    }
    // Initialize distances array with -1 (unreachable)
    const distances = new Array(n + 1).fill(-1);
    distances[s] = 0; // Distance to start node is 0
    // BFS queue
    const queue = [s];
    while (queue.length > 0) {
        const currentNode = queue.shift();
        // Visit all neighbors
        for (const neighbor of adjList[currentNode]) {
            // If neighbor hasn't been visited yet
            if (distances[neighbor] === -1) {
                distances[neighbor] = distances[currentNode] + 6;
                queue.push(neighbor);
            }
        }
    }
    // Remove the start node and node 0 (since nodes start from 1)
    const result = [];
    for (let i = 1; i <= n; i++) {
        if (i !== s) {
            result.push(distances[i]);
        }
    }
    return result;
}