[자료구조][알고리즘] BFS, DFS

BFS

BFS(Breadth First Search)는 그래프 전체를 탐색하는 방법 중의 하나이다. 그래프 전체를 탐색하는 방법은 크게 BFS와 DFS, 두 가지가 있다. 그 둘 중 BFS에 대해 다뤄보고자 한다. 
BFS의 핵심은 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문하도록 구현한다는 점이다. 그리고, 이를 구현하기 위해 queue를 이용한다.

'그래프'를 '시작점을 루트로 하는 트리'라고 생각한다면,"height가 작은 노드부터 차례대로 방문하는 전체 탐색 방식"이다.

swift에선 stl이 없으므로 포인터와 배열을 활용해 구현한다.

구현

func bfsAdjList(_ node: Int, _ edges: [[Int]]) {
  var adjList: [[Int]] = .init(repeating: [], count: node + 1)
  for edge in edges {
    adjList[edge[0]].append(edge[1])
    adjList[edge[1]].append(edge[0])
  }

  var vis: [Bool] = .init(repeating: false, count: node + 1)
  var queue: [Int] = []
  var front = 0

  // 1) 시작하는 노드를 Queue에 넣고 방문했다는 표시를 남김
  queue.append(1)
  vis[1] = true

  while queue.count >= front + 1 {
    // 2) 큐에서 노드를 꺼내고
    let cur = queue[front]
    front += 1
    print(cur)

    // 2) 해당노드와 연결된 노드 중
    for degree in adjList[cur] {
      if vis[degree] { continue } // 이미 방문한 노드인 경우 아무것도 하지않고
      // 처음으로 방문하는 거라면 방문했다는 표시를 남기고 큐에 넣음
      queue.append(degree)
      vis[degree] = true
    }
  }
}

DFS

깊이 우선 탐색은 한 방향으로 갈 수 있을 때까지 가다가 길이 끝나면 가장 가까운 갈림길로 되돌아와 다른 방향을 다시 탐색하는 방식이다.

'그래프'를 '시작점을 루트로 하는 트리'라고 생각한다면, "루트에서 시작하여 가능한 한 깊숙이 노드를 탐색하고, 더 이상 탐색할 노드가 없을 때 이전 분기점(브랜치)으로 돌아가 다른 경로를 탐색하는 전체 탐색 방식"이다.

구현

func dfsAdjList(_ node: Int, _ edges: [[Int]]) {
  var adjList: [[Int]] = .init(repeating: [], count: node + 1)
  for edge in edges {
    adjList[edge[0]].append(edge[1])
    adjList[edge[1]].append(edge[0])
  }

  var vis: [Bool] = .init(repeating: false, count: node + 1)
  var stack: [Int] = []

  // 1) 시작하는 노드를 Stack에 넣고 방문했다는 표시를 남김
  stack.append(1)
  vis[1] = true

  while !stack.isEmpty {
    // 2) Stack에서 노드를 꺼내고
    let cur = stack.removeLast()
    print(cur)

    // 2) 해당노드와 연결된 노드 중
    for degree in adjList[cur] {
      if vis[degree] { continue } // 이미 방문한 노드인 경우 아무것도 하지않고
      // 처음으로 방문하는 거라면 방문했다는 표시를 남기고 Stack에 넣음
      stack.append(degree)
      vis[degree] = true
    }
  }
}

참고
새싹 메모리스
https://sarah950716.tistory.com/13