너비 우선 탐색

이 주제에 대한 튜토리얼은 여기에서 확인할 수 있다.

너비 우선 탐색(BFS, Breadth-First Search)은 트리나 그래프 자료구조를 탐색하거나 순회하는 알고리즘이다. 시작 노드에서 출발해 가장 가까운 이웃 노드를 먼저 탐색한 후, 다음 레벨의 이웃 노드로 이동한다.

너비 우선 탐색은 방향성이 있는 그래프와 방향성이 없는 그래프 모두에 적용할 수 있다.

애니메이션 예제

그래프에서 너비 우선 탐색(BFS)이 어떻게 동작하는지 살펴보자.

노드를 방문하면 검은색으로 표시한다. 동시에 해당 노드의 이웃 노드를 큐에 추가한다. 애니메이션에서는 큐에 추가되었지만 아직 방문하지 않은 노드를 회색으로 표시한다.

애니메이션 예제를 따라가 보자. 시작 노드 A에서 출발해 큐에 추가한다. 애니메이션에서는 노드 A가 회색으로 변하는 것으로 표현된다.

queue.enqueue(A)

이제 큐는 [ A ] 상태가 된다. 큐에 노드가 있는 한, 큐의 맨 앞에 있는 노드를 방문하고, 아직 방문하지 않은 이웃 노드를 큐에 추가하는 방식으로 탐색을 진행한다.

그래프 탐색을 시작하기 위해 큐에서 첫 번째 노드 A를 꺼내고 검은색으로 표시한다. 그런 다음 A의 이웃 노드인 B와 C를 큐에 추가한다. 이때 두 노드는 회색으로 표시된다.

queue.dequeue()   // A
queue.enqueue(B)
queue.enqueue(C)

이제 큐는 [ B, C ] 상태가 된다. B를 큐에서 꺼내고, B의 이웃 노드인 D와 E를 큐에 추가한다.

queue.dequeue()   // B
queue.enqueue(D)
queue.enqueue(E)

큐는 [ C, D, E ] 상태가 된다. C를 큐에서 꺼내고, C의 이웃 노드인 F와 G를 큐에 추가한다.

queue.dequeue()   // C
queue.enqueue(F)
queue.enqueue(G)

큐는 [ D, E, F, G ] 상태가 된다. D를 큐에서 꺼내는데, D는 이웃 노드가 없다.

queue.dequeue()   // D

큐는 [ E, F, G ] 상태가 된다. E를 큐에서 꺼내고, E의 이웃 노드인 H를 큐에 추가한다. B도 E의 이웃 노드이지만 이미 방문했으므로 다시 큐에 추가하지 않는다.

queue.dequeue()   // E
queue.enqueue(H)

큐는 [ F, G, H ] 상태가 된다. F를 큐에서 꺼내는데, F는 방문하지 않은 이웃 노드가 없다.

queue.dequeue()   // F

큐는 [ G, H ] 상태가 된다. G를 큐에서 꺼내는데, G는 방문하지 않은 이웃 노드가 없다.

queue.dequeue()   // G

큐는 [ H ] 상태가 된다. H를 큐에서 꺼내는데, H는 방문하지 않은 이웃 노드가 없다.

queue.dequeue()   // H

이제 큐가 비어있으므로 모든 노드를 탐색한 것이다. 노드를 탐색한 순서는 A, B, C, D, E, F, G, H이다.

이를 트리로 표현할 수 있다.

노드의 부모는 해당 노드를 "발견"한 노드다. 트리의 루트는 너비 우선 탐색을 시작한 노드다.

가중치가 없는 그래프에서 이 트리는 시작 노드에서 트리의 다른 모든 노드까지의 최단 경로를 정의한다. 따라서 너비 우선 탐색은 그래프에서 두 노드 간의 최단 경로를 찾는 한 가지 방법이다.

코드

큐를 사용한 너비 우선 탐색(BFS)의 간단한 구현:

func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var queue = Queue<Node>()
  queue.enqueue(source)

  var nodesExplored = [source.label]
  source.visited = true

  while let node = queue.dequeue() {
    for edge in node.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        queue.enqueue(neighborNode)
        neighborNode.visited = true
        nodesExplored.append(neighborNode.label)
      }
    }
  }

  return nodesExplored
}

큐에 노드가 있는 동안, 첫 번째 노드를 방문하고 아직 방문하지 않은 인접 노드를 큐에 추가한다.

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트할 수 있다:

let graph = Graph()

let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")

graph.addEdge(nodeA, neighbor: nodeB)
graph.addEdge(nodeA, neighbor: nodeC)
graph.addEdge(nodeB, neighbor: nodeD)
graph.addEdge(nodeB, neighbor: nodeE)
graph.addEdge(nodeC, neighbor: nodeF)
graph.addEdge(nodeC, neighbor: nodeG)
graph.addEdge(nodeE, neighbor: nodeH)
graph.addEdge(nodeE, neighbor: nodeF)
graph.addEdge(nodeF, neighbor: nodeG)

let nodesExplored = breadthFirstSearch(graph, source: nodeA)
print(nodesExplored)

출력 결과: ["a", "b", "c", "d", "e", "f", "g", "h"]

BFS는 어떤 경우에 유용할까?

너비 우선 탐색(BFS)은 다양한 문제를 해결하는 데 활용된다. 주요 사례를 살펴보면 다음과 같다:

• 출발 노드와 다른 노드들 간의 최단 경로를 계산할 때 (가중치가 없는 그래프에서만 적용 가능)
• 가중치가 없는 그래프에서 최소 신장 트리를 계산할 때

작성자: Chris Pilcher와 Matthijs Hollemans