[자료구조] 기본적인 그래프 개념

1. 그래프의 정의

그래프라 하면 일반적으로 '정점(노드)'와 '간선(엣지)'으로 이루어진 자료구조를 의미한다. 또한 간선의 방향 유무에 따라서 단방향 그래프와 무방향 그래프(양방향 그래프)로 나뉜다.

---

2. 그래프의 표현

그래프를 표현하는 방식은 크게 인접 행렬 그래프와 인접 리스트 그래프 2가지로 나눌 수 있다. 일반적으로는 인접행렬 방식을 많이 사용하며, 경우에 따라 인접리스트 방식을 사용한다.

2-1. 인접 행렬 그래프 - "모든 정보를 저장"

- 장점 : 직관적이며 쉽게 구현 가능

- 단점 : 불필요한 정보의 저장이 많으며, 그래프의 크기가 커지면 메모리 초과가 발생할 수 있음

- 구현 : int 형의 2차원 배열을 주로 이용하며, 이동할 수 있으면 1, 없으면 0으로 표기함

2-2. 인접 리스트 그래프 - "갈 수 있는 곳만 저장"

- 장점 : 필요한 정보만 저장하여 메모리 절약 가능

- 단점 : 인접행렬에 비해 다소 어려움

- 구현 : 리스트(List)나 벡터(Vector) 등의 자료구조를 이용하여 각 정점에서 이동가능한 정점들을 저장(List나 Vector를 이용한 2차원 배열이라 생각하면 이해하기 쉬움)

---

3. 그래프의 탐색

그래프의 탐색 기법은 크게 4가지, 즉 너비우선탐색(BFS), 깊이우선탐색(DFS), 다익스트라, 플로이드 와샬로 나눌 수 있지만, 기본적인 BFS, DFS만 살펴보겠다.

	너비 우선 탐색 (BFS)	깊이 우선 탐색 (DFS)
탐색 방식	자신과 연결된 주변 정점부터 탐색해 나감	자신과 연결된 정점을 선택해, 그 정점에서 연결된 모든 정점을 파고들어가며 끝날 때까지 들어가 탐색
특징	깊이가 깊은 그래프에 대해 높은 성능	넓이가 넓은 그래프에 대해 높은 성능
제약 조건	너비가 넓은 그래프에 대해 낮은 성능	깊이가 깊은 그래프에 대해 낮은 성능
이용되는 자료구조	큐(Queue)	스택(Stack)
시간 복잡도	인접행렬 : O(V^2) 인접리스트 : O(V + E) (V : 정점의 개수, E : 간선의 개수)

3-1. BFS 탐색

BFS(Breadth First Search, 너비 우선 탐색)는 현재 정점과 연결된 정점들에 대해 우선적으로 넓게 탐색하는 방식이다.

큐(Queue)를 통해 구한하며, 아래로 깊은 그래프에 대해선 좋은 성능을 기대할 수 있으나, 옆으로 넓은 그래프에서는 탐색시간이 오래 걸린다. 

예를 들어 정점 A에서 정점 H를 방문하려 할 때, DFS를 사용하면 한 번에 방문이 가능하나, BFS로는 8번만에 방문이 가능하다.

3-2. DFS 탐색

DFS(Depth First Search, 깊이 우선 탐색)는 현재 정점에서 연결된 정점을 하나 골라 파고들 수 있는 최대한 깊게 파고들어가며 탐색하는 방법이다.

탐색 순서가 약간 난해하게 느껴질 수도 있는데 쉽게 생각해서 "갈 수 있는 길을 찾아 쭉 내려감 -> 더 이상 못가면 1번 되돌아간 뒤 -> 또 갈 수 있는 길을 찾아 쭉 내려감 -> ..." 을 반복한다고 보면 된다.

보통 재귀 호출을 사용하여 구현한다.

옆으로 넓은 그래프에 대해선 준수한 성능을 보이나 아래로 깊은 그래프의 경우 좋은 성능을 기대하기는 힘들다. 

예를 들어 정점 C를 방문하려 할 때, BFS에선 3번만에 방문할 수 있으나, DFS로는 12번만에 방문이 가능하다.

 

 

 

 

본 포스팅은 https://m.blog.naver.com/occidere/220923695595을 참고하여 작성하였습니다.