🤖breadth-first search

🚧 under construction

data structure ⟩ graph ⟩ BFS

Breadth-First Search (BFS)

visits a graph node and explores its neighbors before going on to any of its child nodes. (going wide first before going deep)

  • an iterative algorithm and makes use of a queue. 

// code
// pseudo code
bfs(Graph G, GraphNode root) {

    let q be new Queue
    root.visited = true    // mark root as visited
    q.enqueue(root)        // add root to the queue
 
    while (q is not empty) {
        let current be q.dequeue() // remove front element in the queue
        for(neighbors n of current in G) {
            if (n is not yet visited) {
                // add to the queue - so you can explore its neighbors too
                q.enqueue(n)
                n.visited = true
            }
        }
    }
}
Previous.findShortestPath()Nextdepth-first search

Last updated

Was this helpful?