TIL10: Data Structure - 3 [ Graph ]

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