Breadth-First Algorithm

Sunday, February 19th 2023
// Implementation of a graph as an adjacency list const graph = { A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F"], D: ["B"], E: ["B", "F"], F: ["C", "E"], }; // Implementation of Breadth-First Search function bfs(graph, start) { const visited = {}; const queue = [start]; while (queue.length) { const node = queue.shift(); if (!visited[node]) { visited[node] = true; console.log(node); graph[node].forEach((neighbor) => { if (!visited[neighbor]) { queue.push(neighbor); } }); } } } // Example usage bfs(graph, "A");

In this implementation, graph is represented as an adjacency list where the keys are the nodes and the values are arrays of neighboring nodes. The bfs(graph, start) function performs a BFS traversal of the graph starting at the start node. The visited object keeps track of the nodes that have been visited, and the queue array keeps track of the nodes that are currently being explored.

The bfs(graph, start) function starts by adding the start node to the queue array. Then, while the queue array is not empty, it dequeues the first node in the queue array and checks if it has already been visited. If the node has not been visited, it marks it as visited, logs it to the console, and adds its neighbors to the queue array if they have not been visited already.

In the example usage, bfs(graph, "A") performs a BFS traversal of the graph starting at the node "A". The output of this function would be:

+--- B -----+ / \ A E \ / +--- C --- F--+ \ D