Graph 자료구조

홈 • 게시글 • Today I Learned – TIL • Graph 자료구조
홈 • 게시글 • Today I Learned – TIL • Graph 자료구조

Graph 자료구조

4 답변 글타래를 보이고 있습니다
  • 글쓴이
    글
    • 성훈
      참가자
      • 글작성 : 2
      • 답글작성 : 14

      raywenderlich.com의 Data Structures & Algorithms in Swift책의 Graph를 정리한 글입니다.

      정의

      • 객체 간에 관계를 나타내는 자료구조
      • 여러 객체를 나타내는 점들을 선으로 연결하여 표현한다.
      • 각 점들은 ‘정점’이라고 부르며, 선은 ‘간선’이라고 부른다.
      • 정점간에는 부모 – 자식 개념이 없다.

      그래프 자료구조

      종류

      그래프의 종류는 속성에 관한 것이다. 그래서 가중치 그래프이면서 방향그래프이기도 한다.

      가중치 그래프

      • 간선들은 각각 가중치 값을 가진다.
      • 가중치는 비용, 이동시간, 거리 등 다양한 기준을 활용하여 설정할 수 있으며, 이 가중치를 기준으로 가장 선호되는 경로를 구할 수 있다.

      가중치 그래프

      방향 그래프

      • 간선들이 방향을 가진다.
      • 반드시 단방향으로만 동작하진 않는다.
      • 간선은 정해진 방향으로만 탐색을 허용한다. 그러므로 순회가 제한적이다.

      방향 그래프

      무방향 그래프

      • 모든 간선이 양방향인 방향 그래프이다.
      • 간선의 가중치는 양방향 모두에 적용된다.

      무방향 그래프

      방향 그래프와 무방향 그래프 비교
      방향 그래프와 무방향 그래프 비교

      구현

      • 구현방법은 인접 리스트와 인접 행열 이 두가지가 있다.

      프로토콜 정의

      public enum EdgeType {
 case directed
 case undirected
}
public protocol Graph {
 associatedtype Element
 func createVertex(data: Element) -> Vertex
 //정점을 만들고 그래프에 추가한다.
 func addDirectedEdge(from source: Vertex,
            to destination: Vertex,
            weight: Double?)
 // 방향 간선을 두 정점 사이에 추가한다.
 func addUndirectedEdge(between source: Vertex,
             and destination: Vertex,
             weight: Double?)
 // 무방향 간선을 두 정점 사이에 추가한다.
 func add(_ edge: EdgeType, from source: Vertex,
               to destination: Vertex,
               weight: Double?)
 // EdgeType을 이용하여 방향 또는 무방향 간선을 두 정점 사이에 추가한다.
 func edges(from source: Vertex) -> [Edge]
 // 특정 정점에서 나가는 간선목록을 반환한다.
 func weight(from source: Vertex,
       to destination: Vertex) -> Double?
 // 두 정점 사이에 간선 가중치를 반환한다.
}

      이 프로토콜을 따르는 인접 리스트 그래프와 인접 행열 그래프를 구현할 것이다.

      정점 구현

      public struct Vertex {
 public let index: Int
 public let data: T
}
      • 정점은 그래프에서 고유 인덱스를 가지며 데이터를 보관한다. 
      extension Vertex: Hashable where T: Hashable {}
extension Vertex: Equatable where T: Equatable {}
      • 정점은 키값으로 자주 사용되므로 Hashable을 채택한다.
      • Hashable은 Equatable을 상속하므로 두 프로토콜의 요구사항을 모두 충족해야 한다.

      간선 구현

      public struct Edge {
 public let source: Vertex
 public let destination: Vertex
 public let weight: Double?
}
      • 연결할 출발지와 목적지를 가지며 비용을 옵셔널로 가진다.

      무방향 간선 추가함수 구현

      extension Graph {
 public func addUndirectedEdge(between source: Vertex,
                and destination: Vertex,
                weight: Double?) {
  addDirectedEdge(from: source, to: destination, weight: weight)
  addDirectedEdge(from: destination, to: source, weight: weight)
 } 
}
      • 무방향 간선 추가 함수는 동일하게 적용되므로 프로토콜을 확장하여 구현한다.
      • 무방향 간선은 두개의 방향 간선을 추가하는 것과 같다. 
      extension Graph {
 public func add(_ edge: EdgeType, from source: Vertex,
                  to destination: Vertex,
                  weight: Double?) {
  switch edge { 
  case .directed:
   addDirectedEdge(from: source, to: destination, weight: weight)
  case .undirected:
   addUndirectedEdge(between: source, and: destination, weight: weight)
  } 
 }
}
      • EdgeType를 이용하여 두 정점 사이에 간선을 추가하는 함수도 공통으로 사용가능하므로 프로토콜을 확장하여 구현한다.

      인접 리스트 구현

      • 그래프의 모든 정점에 대한 출발 간선 목록을 저장한다.

      인접 리스트

      public class AdjacencyList: Graph {
 private var adjacencies: [Vertex: [Edge]] = [:]
 public init() {}
 // more to come ...
}
      • 각 정점에 대한 간선 목록을 딕셔너리에 저장한다.
      public func createVertex(data: T) -> Vertex {
 let vertex = Vertex(index: adjacencies.count, data: data) 
 adjacencies[vertex] = []
 return vertex
}
      • 새 정점을 만들고 반환한다. 이 정점을 위한 빈 목록을 인접 리스트에 저장한다.
      public func addDirectedEdge(from source: Vertex,
              to destination: Vertex,
              weight: Double?) {
 let edge = Edge(source: source,
         destination: destination,
         weight: weight) 
 adjacencies[source]?.append(edge)
}
      • 새로운 간선을 만들어 인접리스트에 저장한다.
      public func edges(from source: Vertex) -> [Edge] {
 adjacencies[source] ?? []
}
      • 알지 못하는 정점에 대한 간선 목록은 빈 목록으로 반환한다.
      public func weight(from source: Vertex,
          to destination: Vertex) -> Double? {
 edges(from: source)
  .first { $0.destination == destination }?
  .weight
}
      • 출발지에서 목적지로가는 첫번째 간선을 찾고 그 가중치를 반환한다.

      인접 행열 구현

      • 인접 행열은 그래프를 나타내기 위해 2중 배열을 사용한다.
      • 이 배열은 배열[row][column]의 값은 row와 column에 있는 정점 사이의 가중치를 나타낸다.

      인접 행열

      • 배열의 중간 선은 row와 column이 같은 경우이므로 사용할 수 없다.
      public class AdjacencyMatrix: Graph {
 private var vertices: [Vertex] = []
 private var weights: [[Double?]] = []
 public init() {}
 // more to come ...
}
      • 간선의 목록을 저장하며 가중치를 2중 배열로 저장한다.
      public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: vertices.count, data: data) 
  vertices.append(vertex)
  // 새로운 정점을 목록에 추가한다.
  for i in 0..<weights.count {
  // 지금은 어떠한 간선 없으므로 모든 column에 nil을 추가한다.
    weights[i].append(nil) 
  }
  let row = [Double?](repeating: nil, count: vertices.count)
  // nil값을 담고 있는 새로운 row를 추가한다.
  weights.append(row)
  return vertex
}

      public func addDirectedEdge(from source: Vertex,
              to destination: Vertex, weight: Double?) {
 weights[source.index][destination.index] = weight 
}
      • 출발지와 목적지에 대한 새로운 간선을 2중 배열에 저장한다.
      public func edges(from source: Vertex<T>) -> [Edge<T>] { 
  var edges: [Edge<T>] = []
  for column in 0..<weights.count {
    if let weight = weights[source.index][column] { 
      edges.append(Edge(source: source,
                        destination: vertices[column],
                        weight: weight))
    } 
  }
  return edges
}
      • 정점에 대한 간선을 각 column을 순회하며 탐색한다.
      public func weight(from source: Vertex,
          to destination: Vertex) -> Double? {
 weights[source.index][destination.index] 
}
      • 출발지와 목적지에 대한 가중치는 바로 접근 가능하다.

      그래프 자료구조의 연산자 비용

      연산자 인접 리스트 인접 행열
      저장 공간 O(V + E) O(V^2)
      정점 추가 O(1) O(V^2)
      간선 추가 O(1) O(1)
      정점 및 간선 탐색 O(V) O(1)
      • V는 정점, E는 간선을 의미한다.
      • 인접 리스트는 저장공간을 적게 사용하고 정점을 추가하는데에 유리하다
      • 인접 행열은 정점 및 간선을 탐색하는 데에 속도가 빠르다.

      sparse 그래프
      – 간선이 적은 그래프이다.
      – 간선이 적다는 것은 정점이 상대적으로 많다는 의미이므로, 이에 대한 메모리 공간 소모가 적은 인접 리스트가 유리하다.

      dense 그래프
      – 간선이 많은 그래프이다.
      – 간선의 탐색이 빠른 인접행열이 유리하다.

      Key points

      • 정점과 간선을 통해서 실제 세계의 관계를 나타낼 수 있다.
      • 정점을 객체라고 생각하고 간선을 객체간의 관계라고 생각하자.
      • 가중치 그래프는 모든 간선의 가중치를 연결시킨다.
      • 방향 그래프는 한 방향으로 횡단하는 간선을 가지고 있다.
      • 무방향 그래프는 양 방향을 가리키는 간선을 가지고 있다.
      • 인접 리스트는 모든 정점에서 출발하는 간선 목록을 저장한다.
      • 인접 행렬은 2중 배열을 사용하여 그래프를 나타낸다.
      • 인접 리스트는 일반적으로 적은 간선을 가지고 있는 sparse 그래프에 좋다.
      • 인접 행렬은 일반적으로 많은 간선을 가지고 있는 dense 그래프에 적합하다.

      참고

      • 이 게시글은 야곰에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 게시글은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      2020-03-26 오후 1:31 #4517
    • 야곰
      키 마스터
      • 글작성 : 37
      • 답글작성 : 579

      👍
      글에 보면 어떤 타입은 구조체로, 어떤 타입은 클래스로 구현하였는데 그렇게 선택한 기준이 있는지 궁금합니다!

      2020-03-26 오후 10:54 #4596
    • 성훈
      참가자
      • 글작성 : 2
      • 답글작성 : 14

      구조체로 구현된 부분과 클래스로 구현된 부분을 보면 다음과 같습니다

      구조체: 정점(Vertex), 간선(Edge)
      클래스: 인접 리스트(AdjacencyList), 인접 행열(AdjacencyMatrix)

      결국 자료구조는 클래스로 구현되었으며, 자료구조의 요소들은 구조체로 구현되어 있음을 알 수 있습니다.

      구조체와 클래스는 많은 차이가 있지만, 이번 구현에서 가장 중요한 점은 “같은 데이터를 가지고 있을 때 같은 인스턴스로 볼 수 있는가?” 라고 생각합니다.
      이점에서는 인접리스트와 인접행열 모두 같은 속성을 가져야 하기에, 아래 예시는 인접리스트를 기준으로 하겠습니다.

      아래는 진에어와 아시아나 항공의 항공편을 나타내는 그래프 구조라고 하겠습니다.

      let jin = AdjacencyList<String>()
let asiana = AdjacencyList<String>()

      여기서 만일 jin와 asiana가 동일한 데이터를 담고 있더라도 둘은 나타내고하 하는 점이 다르기 때문에 다른 인스턴스로 보게 될 겁니다.

      let singapore1 = jin.createVertex(data: "Singapore")
let singapore2 = jin.createVertex(data: "Singapore")

      하지만 singapore1가 singapore2 동일한 데이터를 담고 있다면 이 둘은 동일한 데이터를 의미하게 됩니다. 그리고 그래프 자료구조에 동일한 정점을 가지게 되면 스스로에서 출발하여 스스로에게 도착할 수 있어 문제가 발생합니다. 그래서 새로운 정점이 추가될 때, 정점을 인자로 받아 추가하지 않고 자료구조 내부에서 index를 설정하도록 함으로써 자료구조 내부에서 각각의 정점은 고유성을 보장받게 됩니다.
      실제로 singapore1과 singapore2는 같은 “Singapore” 데이터를 가지고 있지만 고유한 index 속성으로 둘은 구분되게 됩니다.

      그 외에도 자료구조는 새로운 정점과 간선에 추가에 열려있고, 정점과 간선은 변경에 닫혀 있도록 구현되어 있다는 점도 둘을 각각 클래스와 구조체로 구현한 요인입니다.

      • 이 답변은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      • 이 답변은 성훈에 의해 4 years, 7 months 전에 수정됐습니다.
      2020-03-27 오전 12:13 #4601
    • 야곰
      키 마스터
      • 글작성 : 37
      • 답글작성 : 579

      네, 제 의견으로는 마지막에 말씀하신 부분이 가장 큰 요인인 것 같습니다. 닫혀있고, 열려있고, 이 둘이 가장 큰 이유라고 생각했습니다.

      애플의 Choosing Between Structures and Classes 문서에서도 많은 힌트를 찾을 수 있을 것 같네요.
      좋은 내용 고맙습니다!

      p.s. 드롭박스에서 이미지가 전부 삭제됐나봐요 +_+ 본문에 이미지가 나오지 않네요 ㅠㅠ

      2020-03-27 오후 1:01 #4626
    • 성훈
      참가자
      • 글작성 : 2
      • 답글작성 : 14

      좋은 말씀 감사합니다! 첨부해 주신 링크가 많은 도움이 되었습니다!

      이미지가 제 사파리브라우저에선 보여서 잘 동작하는 줄 알았는데 캐싱되어서 나오는 것 같네요 ㅠㅡㅠ
      저건 링크를 다른 곳으로 옮겨서 잘 나오게 하도록 바꾸겠습니다

      2020-03-27 오후 1:08 #4635
  • 글쓴이
    글
4 답변 글타래를 보이고 있습니다
  • 답변은 로그인 후 가능합니다.

logo landscape small

사업자번호 : 743-81-02195
통신판매업 신고번호 : 제 2022-충북청주-1278 호
고객센터 : 카카오톡채널 @yagom