Breadth-First Traverse

Breadth-First Search (BFS) is an algorithm used to traverse or search through graph data structures. It explores a graph layer by layer, ensuring that all nodes at the current depth (or distance from the starting point) are explored before moving on to nodes at the next depth level

Adjacency Matrix

function bfsMatrix(graph, start) {
    let queue = [start];
    let visited = new Array(graph.length).fill(false);
    visited[start] = true;

    while (queue.length > 0) {
        let node = queue.shift(); 
        console.log(`Visited node: ${node}`);

        for (let i = 0; i < graph[node].length; i++) {
            if (graph[node][i] === 1 && !visited[i]) {
                visited[i] = true;
                queue.push(i);
            }
        }
    }
}

// Example adjacency matrix
const graphMatrix = [
    [0, 1, 0, 0, 1], 
    [1, 0, 1, 1, 0], 
    [0, 1, 0, 1, 0],
    [0, 1, 1, 0, 1], 
    [1, 0, 0, 1, 0], 
];

bfsMatrix(graphMatrix, 0); 

Adjacency List

function bfsList(graph, start) {
    let queue = [start];
    let visited = new Set();
    visited.add(start);

    while (queue.length > 0) {
        let node = queue.shift(); 
        console.log(`Visited node: ${node}`);

        graph[node].forEach(adjNode => {
            if (!visited.has(adjNode)) {
                visited.add(adjNode);
                queue.push(adjNode);
            }
        });
    }
}


// Example adjacency list
const graphList = [
    [1, 4],    
    [0, 2, 3], 
    [1, 3],    
    [1, 2, 4],
    [0, 3]     
];

bfsList(graphList, 0);