---
description: 🚧 under construction
---

# breadth-first search

[data structure](..) ⟩ [graph]() ⟩ BFS

{% hint style="success" %}
<mark style="color:purple;">**Breadth-First Search**</mark>**&#x20;**<mark style="color:yellow;">**(BFS)**</mark>

visits a graph node and explores its neighbors before going on to any of its child nodes. (<mark style="color:yellow;">**going wide first**</mark> before going deep)

* an **iterative algorithm** and makes use of a **queue**.&#x20;

```javascript
// code
```
{% endhint %}

{% tabs %}
{% tab title="⭐️ 重點" %}
```javascript
// 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
            }
        }
    }
}
```
{% endtab %}

{% tab title="👥 相關" %}
* [queue](../queue "mention") - used in <mark style="color:purple;">**breadth-first search**</mark>.
{% endtab %}

{% tab title="📗 參考" %}
* [ ] MakeUseOf ⟩ [A Guide to the Graph Data Structure](https://www.makeuseof.com/graph-data-structure/)
* [ ] simplilearn ⟩ [Your One-Stop Solution For Graphs In Data Structures](https://www.simplilearn.com/tutorials/data-structure-tutorial/graphs-in-data-structure)
* [ ] Eloqent JavaScript ⟩ [Ch. 7 Project: A Robot](https://eloquentjavascript.net/07_robot.html)&#x20;
* [ ] VisuAlgo ⟩ [GRAPH TRAVERSAL (DFS/BFS)](https://visualgo.net/en/dfsbfs?slide=1)
{% endtab %}
{% endtabs %}
