> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/bfs-breadth-first-search.md).

# BFS(Breadth-First Search)

```
A -> B
|
v
C -> D
```

위 그래프를 distance layer 형태로 나타내면 아래와 같다.

![](/files/-Ly48FYbMIXOMXV_r8GY)

출발 노드를 A라고 했을 때 A의 layer는 0이며 A와 간선 1개로 연결된 C와 B의 layer는 A를 기준으로 1이다. 

![](/files/-Ly48yYDNAzqUoi6XPIh)

초록색으로 된 간선은 그래프의 distance layer에 영향을 주지 않지만, 빨간색 간선의 경우 A와 D의 거리를 2에서 1로 바꾸므로 distance layer 형태를 변하게 한다.

###

### BFS

BFS는 인접한 정점들을 우선으로 탐색하는 방법으로, 큐를 사용한다. **두 정점의 거리(최소 경로)를 구하고자 할 때 사용**하며 의사코드는 아래와 같다.

```python
def BFS(G, start_v):
  for u in V:
    dist[u] = infinity

  start_v = 0

  queue = {start_v} 
  
  while queue is not empty:
    u = dequeue(queue)
    for adj_v in adjacent_vertexes(u):
      if dist[adj_v] == infinity:
        enqueue(adj_v)
        dist[adj_v] = dist[u] + 1
```

#### BFS의 시간복잡도 = O(|E| + |V|) 

각 정점은 최대 1번 큐에 삽입된다. -> while문은 `|V|`만큼 실행한다.

정점 사이의 각 간선을 통해 정점의 방문 여부를 체크한다. -> for문은 총 간선의 갯수만큼 실행한다. 

 (방향없는 그래프는 `간선의 갯수 * 2` 만큼 실행한다.)

### 최단 경로 트리 (Shortest-path Tree)

최단 경로 트리는 방향없는 그래프 내의 각 정점 사이의 거리(최단 경로)를 트리로 나타낸다. 어떤 정점 `S`를 시작으로 BFS를 실행하고나서 각 정점에서 `S`로의 최단 경로를 저장한다. 트리의 루트는 `S`가 된다. 

![그래프와 최단 경로 트리](/files/-Ly4c90EOEGbgbOta8Z2)

방향없는 그래프의 정점 `S`에서 `B`로 가는 최단 경로는 `B`에서 `S`로 가는 최단 경로와 같다. 따라서 각 정점에서 `S`로 향하는 최단 경로를 트리 형태로 만든 것이 최단 경로 트리다. 예를 들어, `B`에서 `S`로 향하는 최단 경로는 3이다. 

최단 경로 트리를 사용하면

* 두 정점의 거리(최단 경로)를 구할 수 있다.
* `S` -> `A` 의 최단 경로를 통해 `A` -> `S` 의 최단 경로를 구할 수 있다.
* 어느 정점을 시작점으로 하여 모든 정점과의 최단 경로들을 구할 수 있다.

최단 경로 트리의 중요한 특징 중 하나는 트리로 나타내는 그래프에 사이클이 없다는 것이다.

![](/files/-Ly4SnpSx5eel-VjJYJQ)

정점 `S`와 `A`의 거리(최단 경로)가 `d`라고 했을 때 `A`는 다른 정점 B, C, D, E와 사이클을 이룬다고 가정해보자. `A`에서 `S`로 향하는 최단 경로는 `S`에서 `A`로 향하는 최단 경로와 같다. 따라서 `A`에서 출발하여 다른 정점으로 이동할 때마다 `d`를 1씩 감소시켜 S에 도착했을 때 0이 되는지 확인하려고 한다.

![](/files/-Ly4_qnc6-xCPNrVtue5)

A, B, C, D, E가 사이클을 이룰 때 무한으로 `d`가 감소되므로 `A`에서 `S`로 향하는 최단 경로는 마이너스 무한대가 될 것이다. 이는 `A`에서 `S`로 향하는 최단 경로가 `d`라는 가정과 모순되므로 최단 경로 트리에 사이클이 존재하지 않음을 증명한다. 

  아래는 `prev` 배열에 이전에 방문했던 정점을 저장하여 최단 경로 트리를 만드는 코드다.

```python
def BFS(G, start_v):
  for u in V:
    dist[u] = infinity
    prev[u] = nil

  start_v = 0

  queue = {start_v} 
  
  while queue is not empty:
    u = dequeue(queue)
    for adj_v in adjacent_vertexes(u):
      if dist[adj_v] == infinity:
        enqueue(adj_v)
        dist[adj_v] = dist[u] + 1
        prev[adj_v] = u


# u에서 S로 향하는 최단 경로를 구한다.
# 예) ConstructPath(S, G, prev) -> (G, B, A, S) 리턴 
def ConstructPath(S, u, prev):
  result = empty
  
  while u != S:
    result.append(u)
    u = prev[u]
  
  return reverse(result)    
```

최단 경로 트리를 이용하여 두 정점의 최단 경로를 구할 때 시간복잡도는 `O(|V| + |E|)` 이다.

출처

* [코세라 알고리즘 ](https://www.coursera.org/learn/algorithms-on-graphs?specialization=data-structures-algorithms)