BFS(Breadth-First Search)

A -> B
|
v
C -> D

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

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

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

BFS

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

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가 된다.

그래프와 최단 경로 트리

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

최단 경로 트리를 사용하면

• 두 정점의 거리(최단 경로)를 구할 수 있다.

• S -> A 의 최단 경로를 통해 A -> S 의 최단 경로를 구할 수 있다.

• 어느 정점을 시작점으로 하여 모든 정점과의 최단 경로들을 구할 수 있다.

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

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

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

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

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|) 이다.

출처

• 코세라 알고리즘