Data Structure | Graph (js)

그래프 (Graph)

: 정점(vertex)와 간선(edge)으로 나타냄
2가지 방식으로 구현

• 인접 행렬(adjacency matrix): 2차원 배열을 사용하는 방식
  

모든 정점들의 연결 여부를 저장해 O(V^2)의 메모리 필요
하지만 두 노드의 연결 여부를 O(1)에 확인 가능
-무방향 무가중치 그래프: 모든 간선이 방향성을 가지지 않고, 가중치도 없음

-방향 가중치 그래프: 모든 간선이 방향, 가중치를 가지는 그래프

• 인접 리스트(adjacency list): 연결 리스트를 이용하는 방식

-무방향 무가중치 그래프

-방향 가중치 그래프

연결된 간선의 정보만 저장해 O(V+E)의 메모리 필요
하지만 두 노드의 연결 여부를 확인하려면 O(V)의 시간 필요