From the course: Data Structures in JavaScript: Trees and Graphs

Unlock this course with a free trial

Join today to access over 25,500 courses taught by industry experts.

Breadth-first search implementation

Breadth-first search implementation

From the course: Data Structures in JavaScript: Trees and Graphs

Start my 1-month free trial Buy for my team

Breadth-first search implementation

“

- [Instructor] Now that we've explored how Breadth-First Search works conceptually, it's time to implement it in JavaScript. We'll use a queue to traverse the graph level-by-level while maintaining a visited set to prevent infinite loops. This hands-on coding exercise will reinforce how BFS efficiently finds the shortest path in an unweighted graph. Here I have an adjacency list. It represents a disconnected undirected graph in the lines above. Our BFS function needs to traverse its immediate neighbors through the adjacency list to find a target before going through its neighbor's neighbors. First, we always need a queue for BFS. Second, since it's a graph, we need to create a visited set to keep track of visited nodes and to avoid infinite loops. Third, we will loop through each node in adjacency list and in queue the current node. If the node has not been visited, we in queue the node. Then while the queue is not empty, we deque the current value, check if the current value is the…

Contents