[Swift] DFS/BFS

 

DFS - 깊이 우선 탐색

let graph = [
    [], // 0
    [2,3], // 1
    [1,4,5], // 2
    [1,6,7], // 3
    [2], // 4
    [2], // 5
    [3], // 6
    [3,8], // 7
    [7] // 8
]

var visited = Array.init(repeating: false, count: graph.count)

func dfs(start: Int) {
  visited[start] = true
  
  print(start, terminator: " ")
  
  for i in graph[start] {
    if !visited[i] {
      dfs(start: i)
    }
  }
}

dfs(start: 1)

 

BFS - 너비 우선 탐색

let graph = [
    [], // 0
    [2,3], // 1
    [1,4,5], // 2
    [1,6,7], // 3
    [2], // 4
    [2], // 5
    [3], // 6
    [3,8], // 7
    [7] // 8
]

var visited = Array.init(repeating: false, count: graph.count)

var queue = Queue<Int>()

func bfs(start: Int) {
  queue.enquque(start)
  visited[start] = true
  
  while !queue.isEmpty {
    guard let elem = queue.dequeue() else { return }
    print(elem, terminator: " ")
    
    for i in graph[elem] {
      if !visited[i] {
        queue.enquque(i)
        visited[i] = true
      }
    }
  }
}

public struct Queue<T> {
  fileprivate var array = [T]()
  
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }
  
  public mutating func enquque(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}

bfs(start: 1)​