Medium Graphs
BFS Graph
Traverses a graph breadth-first starting from node 0, using an explicit FIFO queue: it visits the start node, then all of its direct neighbors, then their unvisited neighbors, expanding outward one ring at a time — the same building block used to find shortest paths in unweighted graphs. Receives the graph as a square adjacency matrix, where a nonzero value at row i, column j marks an edge between nodes i and j (0 means no edge). Returns the node indices in the order they were visited; nodes unreachable from node 0 are never visited.
Visualization
- Input
- Result
Algorithm code
// BFS Graph — a single pure function. Receives a graph as an N×N adjacency
// matrix and returns the breadth-first traversal order of node indices
// starting from node 0, using an explicit FIFO queue.
/**
* @param {number[][]} adjacencyMatrix - N×N matrix where a truthy value at
* row i, column j marks an edge between nodes i and j
* @returns {number[]} node indices in breadth-first visit order from node 0
*/
export function bfsGraph(adjacencyMatrix) {
const nodeCount = adjacencyMatrix.length;
const order = [];
if (nodeCount === 0) {
return order;
}
const visited = new Array(nodeCount).fill(false);
const queue = [0];
visited[0] = true;
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (let neighbor = 0; neighbor < nodeCount; neighbor += 1) {
if (adjacencyMatrix[node][neighbor] && !visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
return order;
}FUNCTION bfsGraph(adjacencyMatrix):
nodeCount ← length(adjacencyMatrix)
order ← empty list
IF nodeCount = 0:
RETURN order
visited ← array of nodeCount false values
queue ← [0]
visited[0] ← true
WHILE queue is not empty:
node ← dequeue from queue
append node to order
FOR neighbor FROM 0 TO nodeCount - 1:
IF adjacencyMatrix[node][neighbor] AND NOT visited[neighbor]:
visited[neighbor] ← true
enqueue neighbor to queue
RETURN order