> For the complete documentation index, see [llms.txt](https://lochiwei.gitbook.io/web/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lochiwei.gitbook.io/web/appendix/data/graph/bfs.md).

# breadth-first search

🚧 under construction

[data structure](/web/appendix/data.md) ⟩ [graph](/web/appendix/data/graph.md) ⟩ 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](/web/appendix/data/queue.md) - 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 %}