🤖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
            }
        }
    }
}

👥 相關

• Queue - used in breadth-first search.

📗 參考

• MakeUseOf ⟩ A Guide to the Graph Data Structure

• simplilearn ⟩ Your One-Stop Solution For Graphs In Data Structures

• Eloqent JavaScript ⟩ Ch. 7 Project: A Robot

• VisuAlgo ⟩ GRAPH TRAVERSAL (DFS/BFS)