Graph(그래프)

  • 특징: Vertex(정점 또는 노드(Node)), 그리고 노드와 노드를 연결하는 Edge(간선)으로 구성되는 자료 구조
  • 종류
    • 방향성: Undirected(무방향성), Directed(방향성)
    • 구현방식: ** Adjacency Matrix(인접 행렬)**, Adjacency List(인접 리스트)
  • 구현 구조
    • 인접 리스트: 각 노드를 key, 그리고 간선들을 element로 가지는 Array를 value로 하는 Object 구조
    • 인접 행렬: 각 노드들을 행과 열로 가지는 2차원 Array 구조

  • <인접 리스트> Big O 표기
    • 가져오기: O(V)
    • 정점 추가하기: O(1)
    • 정점 삭제하기: O(V+E)
    • 간선 추가하기: O(1)
    • 간선 삭제하기: O(E)
  • <인접 행렬> Big O 표기
    • 가져오기: O(1)
    • 정점 추가하기: O(V**2)
    • 정점 삭제하기: O(V**2)
    • 간선 추가하기: O(1)
    • 간선 삭제하기: O(1)

자료 출처: javatpoint.com

0개의 댓글