[자료구조] 그래프(Graph)와 탐색(Search)

🌱 그래프

그래프 ❘ 인접 행렬, 인접 리스트

 

그래프는 노드와 간선으로 이루어진 자료 구조이다. 크게 노드와 엣지(간선)으로 구성되어 있다.

그래프는 간선으로 연결된 노드들 간 이동할 수 있는데, 이렇게 간선으로 연결된 노드들을 인접하다(Adjacent)고 한다.

 

 

🌱 그래프 표현 방법

그래프에서 인접한 노드들간의 관계를 나타내는 방법으로 크게 인접 행렬(Adjacency matrix)과 인접 리스트(adjacency list)가 있다.

1. 인접 행렬

인접 행렬은 단어 그대로 "행렬"의 형태로 인접한 노드 간의 관계를 나타낸 것을 의미한다.

행의 노드와 열의 노드 간의 거리를 행렬값으로 확인할 수 있다. 따라서 인접한 노드 조회를 할 때 시간 측면에서 O(1)로 아주 빠르다.

그러나 이 방식은 메모리 측면에서 비효율성을 야기할 수 있기에 조심해야 한다. 모든 노드에 대해 행렬을 표현하기 때문에 노드의 수가 많아질 수록 많은 메모리를 소모한다.

 

2. 인접 리스트

인접 리스트는 "연결 리스트"를 이용하여 인접한 노드 간의 관계를 나타낸다.

각각의 노드에 대하여 연결된 노드에 대한 값만 존재하므로 메모리 측면에서 효율적이라는 것을 알 수 있다.

그러나 어떠한 두 노드가 인접한 지 조회할 때엔 어느 한 쪽 노드에 연결된 모든 노드를 조회해보아야 하므로 최악의 경우 O(n)으로, 시간이 오래 걸릴 수 있다.

 

상황이나 주어진 조건에 따라 위 두 가지 방법 중 더 유리한 것을 선택할 수 있어야 한다.

실제 코딩 테스트 상황에서 잘 선택할 수 있도록 평소에 잘 익혀두어야겠다.