[Algorithms] Breadth-First Search (BFS) | 너비 우선 탐색

Breadth-First Search (BFS)

너비 우선 탐색

- 그래프 상의 모든 Vertex를 탐색하는 알고리즘 중 하나이다.
- 시작 Vertex에 인접한 Vertex를 모두 방문하고, 인접한 Vertex에 인접해 있는 Vertex를 방문해 나아간다.
- Tree에서 BFS를 수행하면, Root부터 Tree의 Level 순서대로 Traversal하게 된다.

* Graph (그래프) (URL)

[Data Structures] Graph | 그래프

Example. BFS vs DFS in Tree Structure

* Depth-First Search (DFS) (깊이 우선 탐색) (URL)

[Algorithms] Depth-First Search (DFS) | 깊이 우선 탐색

---

Mechanism (원리)

Phase	Description
(a)	- 시작 정점으로 정해진 정점을 방문한다.   (이 때 방문한 정점이 1로 표시된다.)
(b)	- (a) 단계에서 방문한 정점에 인접한 정점을 모두 방문한다.   (이 때 방문한 정점들이 2, 3, 4로 표시된다.)
(c)	- (b) 단계에서 새로 방문한 정점들(2, 3, 4)에 인접한 정점들을 모두 방문한다. - 정점 2에 인접한 정점들 중 방문하지 않은 정점들은 없으므로 넘어간다. - 정점 3에 인접한 정점들 중 방문하지 않은 하나의 정점이 있으므로,   이 정점을 방문한다.   (이 때 방문한 정점이 5로 표시된다.) - 정점 4에 인접한 정점들 중 방문하지 않은 두 정점들이 있으므로,   이 정점들을 방문한다.   (이 때 방문한 정점들이 6, 7로 표시된다.)
(d)	- (c) 단계에서 새로 방문한 정점들(5, 6, 7)에 인접한 정점들을 모두 방문한다. - 정점 5에 인접한 정점들 중 방문하지 않은 정점들은 없으므로 넘어간다. - 정점 6에 인접한 정점들 중 방문하지 않은 하나의 정점이 있으므로,   이 정점을 방문한다.   (이 때 방문한 정점이 8로 표시된다.) - 정점 7에 인접한 정점들 중 방문하지 않은 정점들은 없으므로 넘어간다.
(e)	- (d) 단계에서 새로 방문한 정점(8)에 인접한 정점들에 대한 방문을 시도한다. - 그러나, 마지막 정점인 8에 인접한 정점들 중 방문하지 않은 정점은 없으므로   BFS를 종료한다.

* Breadth-First Tree (너비 우선 트리)
- BFS에서 정점들을 방문할 때 거쳤던 Edge들의 집합이다.
- 위 BFS 수행 예시 그림에서, 검은색 굵은 실선들에 해당되는 Edge들을 모으면
  너비 우선 트리가 구성된다.
- 너비 우선 트리는 Spanning Tree(신장 트리)에 속한다.

Example. BFS on an undirected graph

---

Implementation (구현)

* GitHub (URL)

* Pseudo Code

BFS(G, s)
// G : Given Graph
// s : Starting Vertex
// Q : Queue
// L(u) : Set for Adjacency Vertices of Vertex 'u'
{
    for(v ∈ V - {s})
        visited[v] = FALSE;
    
    visited[s] = TRUE;
    enqueue(Q, s);
    
    while(Q is not empty) {
        u = dequeue(Q);
        for(v ∈ L(u))
            if(visited[v] == FALSE) {
                visited[v] = TRUE;
                enqueue(Q, v);
            }
    }
}

---

Performance (성능)

Time Complexity : \(\Theta(|V|+|E|)\)
\(V\) : Set of Vertices of Graph \(G\)
\(E\) : Set of Edges of Graph \(G\)

- BFS에서는 시작 정점으로 부터 모든 정점들을 한 번은 방문해야 하며,
  그 과정에서 모든 간선들도 한 번 이상은 거쳐가게 된다.

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)