Swift로 연습하는 너비우선탐색(Breadth-First Search)

This topic has 1개 답변, 2명 참여, and was last updated 4 years, 8 months 전에 by 야곰.

1 답변 글타래를 보이고 있습니다

글쓴이

글

련호 김

참가자

글작성 : 1
답글작성 : 0

그래프의 vertice를 탐색하는 방법에 여러가지가 있지만, 아래와 같은 문제를 해결하기 위해서 BFS 알고리즘이 사용됨.

최소 스패닝 트리 생성
vertice 간의 경로 찾기
두 vertice 간의 최단 경로 찾기

간단한 예제
BFS는 하나의 노드을 기준으로 시작함.
그리고 그 노드을 기준으로 근접한 노드들을 모두를 먼저 방문(visit)함.
근접한 노드를 먼저 방문하기 위해서 큐를 이용함.

그래프 초기 상태

첫 번째로 방문할 노드A 선택 및 큐 삽입

큐의 가장 상단에 있는 노드(노드A)에 방문하고 노드A에 근접한 노드들을 모두 큐에 삽입 (큐에 삽입할때 이미 방문했거나, 이미 큐에 있는 노드를 다시 삽입하지 않도록 처리 필요함)

큐의 가장 상단 노드B를 방문 → B의 근접 노드를 큐에 삽입
그리고 계속 반복(큐의 최상단 노드를 꺼내서 방문하고, 그 노드의 인접노드를 큐에 삽입)

시작노드를 기준으로 너비우선탐색 순서를 연결하면 (논리적으로) 트리를 얻을 수 있습니다. 각 레벨은 너비 탐색의 레벨을 의미합니다.

구현 코드

import UIKit

// #############################################################################
// 기존 그래프 구현부
public struct Vertex<T> {
  public let index: Int
  public let data: T
}

extension Vertex: Hashable where T: Hashable {}
extension Vertex: Equatable where T: Equatable {}
extension Vertex: CustomStringConvertible {
  public var description: String {
    "\(index): \(data)"
  }
}

public struct Edge<T> {
  public let source: Vertex<T>
  public let destination: Vertex<T>
  public let weight: Double?
}

public enum EdgeType {
  case directed
  case undirected
}

public protocol Graph {
  associatedtype Element

  func createVertex(data: Element) -> Vertex<Element>
  func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
  func addUndirectedEdge(between source: Vertex<Element>, and destination: Vertex<Element>, weight: Double?)
  func add(_ edge: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
  func edges(from source: Vertex<Element>) -> [Edge<Element>]
  func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
}

extension Graph {

  public func addUndirectedEdge(between source: Vertex<Element>, and destination: Vertex<Element>, weight: Double?) {
    addDirectedEdge(from: source, to: destination, weight: weight)
    addDirectedEdge(from: destination, to: source, weight: weight)
  }

  public func add(_ edge: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
    switch edge {
      case .directed:
        addDirectedEdge(from: source, to: destination, weight: weight)
      case .undirected:
        addUndirectedEdge(between: source, and: destination, weight: weight)
    }
  }


}


public class AdjacencyList<T: Hashable>: Graph {
  private var adjacencies: [Vertex<T>: [Edge<T>]] = [:]
  public init() {}

  public func createVertex(data: T) -> Vertex<T> {
    let vertex = Vertex(index: adjacencies.count, data: data)
    adjacencies[vertex] = []
    return vertex
  }

  public func addDirectedEdge(from source: Vertex<T>, to destination: Vertex<T>, weight: Double?) {
    let edge = Edge(source: source, destination: destination, weight: weight)
    adjacencies[source]?.append(edge)
  }

  public func edges(from source: Vertex<T>) -> [Edge<T>] {
    adjacencies[source] ?? []
  }

  public func weight(from source: Vertex<T>, to destination: Vertex<T>) -> Double? {
    edges(from: source)
      .first { $0.destination == destination }?
      .weight
  }
}

extension AdjacencyList: CustomStringConvertible {
  public var description: String {
    var result = ""
    for (vertex, edges) in adjacencies { // 1
      var edgeString = ""
      for (index, edge) in edges.enumerated() { // 2
        if index != edges.count - 1 {
          edgeString.append("\(edge.destination), ")
        } else {
          edgeString.append("\(edge.destination)")
        }
      }
      result.append("\(vertex) ---> [ \(edgeString) ]\n") // 3
    }
    return result
  }
}


// #############################################################################
// 너비 우선 검색 - BFS

extension Graph where Element: Hashable {
  func breadthFirstSearch(from source: Vertex<Element>) -> [Vertex<Element>] {

    var queue: [Vertex<Element>?] = []// 큐
//  var queue = QueueStack<Vertex<Element>>() // 큐

    var enqueued: Set<Vertex<Element>> = []   // 중복 방문을 체크하기 위한 Set
    var visited: [Vertex<Element>] = []       // 방문한 노드 배열(방문 순서대로)

    queue.append(source)   // 큐에 초기 노드 삽입
//  queue.enqueue(source)   // 큐에 초기 노드 삽입

    enqueued.insert(source)

    while !queue.isEmpty, let vertex = queue.removeFirst() { // 큐에서 하나 꺼냄
//  while let vertex = queue.dequeue() { // 큐에서 하나 꺼냄

      visited.append(vertex) // 방문
      let neighborEdges = edges(from: vertex) // 인접한 노드 확인
      neighborEdges.forEach { edge in
        if !enqueued.contains(edge.destination) { // 이미 방문했거나, 큐에 들어가 있는지 체크
          queue.append(edge.destination)         // 처음 발견된 노드라면 큐에 삽입
//        queue.enqueue(edge.destination)        // 처음 발견된 노드라면 큐에 삽입
          enqueued.insert(edge.destination)
        }
      }
    }

    return visited
  }
}

let graph = AdjacencyList<String>()
let A = graph.createVertex(data: "A")
let B = graph.createVertex(data: "B")
let C = graph.createVertex(data: "C")
let D = graph.createVertex(data: "D")
let E = graph.createVertex(data: "E")
let F = graph.createVertex(data: "F")
let G = graph.createVertex(data: "G")
let H = graph.createVertex(data: "H")
graph.add(.undirected, from: A, to: B, weight: 0)
graph.add(.undirected, from: A, to: C, weight: 0)
graph.add(.undirected, from: A, to: D, weight: 0)
graph.add(.undirected, from: B, to: E, weight: 0)
graph.add(.undirected, from: C, to: F, weight: 0)
graph.add(.undirected, from: C, to: G, weight: 0)
graph.add(.undirected, from: E, to: H, weight: 0)
graph.add(.undirected, from: E, to: F, weight: 0)
graph.add(.undirected, from: F, to: G, weight: 0)
print(graph)

let vertices = graph.breadthFirstSearch(from: A)
vertices.forEach { vertex in
  print(vertex)
}




// #############################################################################
// Chapter 39 BFS Challenge2 - iterative 코드를 recursive 코드로 작성

extension Graph where Element: Hashable {
  func bfs2(from source: Vertex<Element>) -> [Vertex<Element>] {
    var queue: [Vertex<Element>?] = []
    var enqueued: Set<Vertex<Element>> = []
    var visited: [Vertex<Element>] = []

    queue.append(source)
    enqueued.insert(source)

    bfs(queue: &queue, enqueued: &enqueued, visited: &visited)

    return visited
  }
  private func bfs(queue: inout [Vertex<Element>?], enqueued: inout Set<Vertex<Element>>, visited: inout [Vertex<Element>]) {
    guard !queue.isEmpty, let vertex = queue.removeFirst() else {
      return
    }
    visited.append(vertex)
    let neighborEdges = edges(from: vertex)

    neighborEdges.forEach { edge in
      if !enqueued.contains(edge.destination) {
        queue.append(edge.destination)
        enqueued.insert(edge.destination)
      }
    }

    bfs(queue: &queue, enqueued: &enqueued, visited: &visited)
  }
}


let vertices = graph.bfs2(from: A)
vertices.forEach { vertex in
  print(vertex)
}

// #############################################################################
// Chapter 39 BFS Challenge3 - 단절된 부분이 있는지 확인하는 함수작성

extension AdjacencyList {
  func isDisconnected() -> Bool {
    guard let (firstVertex, _) = adjacencies.first else { // 1
      return false
    }
    let visited = breadthFirstSearch(from: firstVertex) // 2
    for (vertex, _) in adjacencies { // 3
      if !visited.contains(vertex) {
        return true
      }
    }
    return false
  }
}

print("isDisconnected: \(graph.isDisconnected())")

퍼포먼스
그래프를 순회하면서 각 노드는 한번씩만 큐에 추가됨 → O(V) 그래프를 순회하면서 모든 edge를 한번씩 거쳐가야함 → O(E)

O(V + E) 공간 복잡도는, 노드들을 모두 저장해야하기 때문에 O(3V) → O(V)

키 포인트
너비 우선 검색 (BFS)은 그래프를 탐색하거나 검색하기 위한 알고리즘입니다. BFS는 다음 정점을 통과하기 전에 현재 정점의 모든 이웃을 탐색합니다. 그래프 구조에 인접 정점이 많이 있거나 가능한 모든 결과를 찾아야 할 때 이 알고리즘을 사용하는 것이 좋습니다. 큐 데이터 구조는 레벨을 더 깊이 다이빙하기 전에 정점의 주변 모서리를 통과하는 우선 순위를 지정하는 데 사용됩니다.

이 게시글은 련호 김에 의해 4 years, 8 months 전에 수정됐습니다.
이 게시글은 련호 김에 의해 4 years, 8 months 전에 수정됐습니다.
이 게시글은 련호 김에 의해 4 years, 8 months 전에 수정됐습니다.
이 게시글은 련호 김에 의해 4 years, 8 months 전에 수정됐습니다.
이 게시글은 련호 김에 의해 4 years, 8 months 전에 수정됐습니다.

야곰
키 마스터

글작성 : 37
답글작성 : 579

양질의 글 멋집니다! 👍
2020-03-29 오후 10:09 #4991

글쓴이

글

1 답변 글타래를 보이고 있습니다

답변은 로그인 후 가능합니다.