Javascript/자료구조

[Javascript] 자료구조 - 그래프(Graph)

BeomBe 2023. 11. 24. 14:25
반응형

그래프(Graph)

사물의 정점(vertex)과 간선(edge)으로 나타내기 위한 도구

 

그래프는 두가지 방식으로 구현

1. 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 (각각 노드에서 노드로 움직일 때 드는 비용)

 

인접행렬 - 무방향 무가중치 그래프

모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.

모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다.

무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력

 

인접 행렬 - 방향 가중치 그래프

모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.

모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.

방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.

 

2. 인접 리스트(adjacency list) : 연결 리스트를 이용하는 방식 -- 일반적인 그래프 문제(최단경로)

그래프를 리스트로 표현

 

인접 리스트 - 무방향 무가중치 그래프

인덱스 마다 표현 (인덱스 0 : 0에서 갈수있는 값, 1,2)

 

인접 리스트 - 방향 가중치 그래프

 

그래프의 시간 복잡도

1. 인접 행렬 : 모든 정점들의 연결 여부를 저장해 O(V²)의 공간을 요구

- 공간 효율성이 떨어지지만, 두 노드의 연결여부를 O(1)에 확인

2. 인접 리스트 : 연결된 간선의 정보만 저장 O(V + E)의 공간을 요구

- 공간 효율성이 우수하지만, 두 노드의 연결여부를 확인하기 위해 O(V)시간이 필요

반응형
댓글수1