깊이 우선 탐색(DFS)

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

깊이 우선 탐색(DFS, Depth-First Search)은 트리나 그래프 데이터 구조를 탐색하거나 순회하는 알고리즘이다. 시작 노드에서 출발해 각 분기를 따라 가능한 한 깊이 탐색한 후, 더 이상 진행할 수 없을 때 되돌아온다.

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

애니메이션 예제

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

노드 A에서 탐색을 시작한다고 가정하자. 깊이 우선 탐색에서는 시작 노드의 첫 번째 이웃을 방문한다. 이 예제에서는 노드 B를 방문한다. 그다음 노드 B의 첫 번째 이웃을 방문한다. 이 경우 노드 D를 방문한다. 노드 D는 더 이상 방문할 이웃이 없기 때문에, 노드 B로 되돌아가 다른 이웃인 노드 E를 방문한다. 이 과정을 그래프의 모든 노드를 방문할 때까지 반복한다.

매번 첫 번째 이웃을 방문하고 더 이상 갈 곳이 없을 때까지 진행한 후, 다시 방문할 노드가 있는 지점으로 되돌아간다. 노드 A로 완전히 되돌아오면 탐색이 종료된다.

이 예제에서 노드는 A, B, D, E, H, F, G, C 순서로 방문된다.

깊이 우선 탐색 과정은 트리로 시각화할 수도 있다.

노드의 부모는 해당 노드를 "발견"한 노드다. 트리의 루트는 깊이 우선 탐색을 시작한 노드다. 분기점이 나타날 때마다 되돌아가는 지점이다.

코드

깊이 우선 탐색(DFS)을 간단히 재귀적으로 구현한 코드:

func depthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var nodesExplored = [source.label]
  source.visited = true

  for edge in source.neighbors {
    if !edge.neighbor.visited {
      nodesExplored += depthFirstSearch(graph, source: edge.neighbor)
    }
  }
  return nodesExplored
}

너비 우선 탐색(BFS)은 모든 인접 노드를 먼저 방문하는 반면, 깊이 우선 탐색은 트리나 그래프에서 가능한 한 깊이 들어가려고 한다.

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

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 = depthFirstSearch(graph, source: nodeA)
print(nodesExplored)

이 코드의 실행 결과는 다음과 같다: ["a", "b", "d", "e", "h", "f", "g", "c"]

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

깊이 우선 탐색(DFS)은 다양한 문제를 해결하는 데 활용된다. 주요 사례는 다음과 같다:

• 희소 그래프의 연결 요소 찾기
• 그래프 노드의 위상 정렬
• 그래프의 브릿지 찾기 (참고: 브릿지)
• 기타 여러 문제 해결

Swift Algorithm Club의 Paulo Tanaka와 Matthijs Hollemans가 작성