DFS, BFS를 공부하기 전 먼저 그래프에 대해 간략하게 정리하고자 한다.
그래프란, 위 그림과 같이 정점(vertex)과 간선(edge)로 이루어진 자료구조이다.
간선은 정점의 ordered pair로 표현한다. 예를들어 (u,v)는 u에서 v로 향하는 간선을 뜻한다.
그래프는 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 나뉘어진다.
방향 그래프에서 간선은 방향성을 가지고 있으며, 화살표 모양으로 표현된다.
directed graph에서는 self-loop(자기 자신에서 자기 자신을 가리키는 간선)도 가능하다.
1. Adjacency
간선 (u,v)가 있을 때, 정점 v를 정점 u의 adjacency라고 한다.
undirected graph에서는 인접 관계가 대칭적이며, directed graph에서는 비대칭적이다.
2. Degree(차수)
out-degree는 한 정점에서 나가는 간선의 수를 뜻하며, in-degree는 한 정점에 들어오는 간선의 수를 뜻한다.
degree = out-degree + in-degree 이다.
undirected graph에서는 out-degree와 in-degree가 정의되지 않으며 오직 degree만 정의된다.
3. Path
path란, 정점들의 시퀀스를 의미한다.
u에서 v로 가는 path <v0, v1, v2, ..., vk>가 있을 때,
- v0 = u, vk = v
- 모든 이웃한 정점 사이에 간선이 존재함
을 의미한다.
쉽게 말해 위와 같은 그래프에서 <1,0,3>은 패스이며, <3,4,0>도 패스지만 <1,0,4>는 패스가 아니다. (간선 (0,4)가 존재하지 않으므로)
경로에 있는 모든 정점들이 한번씩만 나올 때, 그 path를 simple path라고 한다.
예를 들어 <0,2,1>은 simple path지만 <0,2,1,0,2>는 simple path가 아니다.
4. Cycle
path <v0, v1, v2, ..., vk>에서 v0 = vk 일 때, 이것을 사이클이라고 한다. 쉽게 말해 출발 지점과 도착 지점이 같은 path가 사이클이다.
또한 v0를 제외한 모든 정점들이 중복되지 않는다면 이것을 simple cycle이라고 한다.
그래프의 표현방법
그래프를 컴퓨터 자료구조로 표현하기 위해서는 두가지 방법이 있다.
adjacency-list(인접리스트)를 사용하는 방법, adjacency-matrix(인접행렬)를 사용하는 방법이다.
위의 그림에서 (b)가 인접리스트를 이용한 방법, (c)가 인접행렬을 이용한 방법이다.
1. 인접리스트
인접리스트란, 연결 리스트를 이용해서 그래프를 표현하는 방법이다.
정점의 개수만큼의 크기를 가지는 배열을 선언한 뒤(각각의 배열 원소는 정점을 나타낸다),
각 정점에서 연결된 정점을 연결 리스트를 이용해서 연결하는 방식이다.
directed graph의 경우, 간선에 방향성이 존재하므로 나가는 간선에 대해서만 인접 리스트를 만들어주면 되지만
undirected graph의 경우, 방향성이 존재하지 않으므로 그냥 한 정점에서 연결된 모든 간선에 대해 인접리스트를 만들어주면 된다. 이렇게 되면 하나의 간선은 인접 리스트에 두 번 나타나게 된다.
공간복잡도는 Θ(V+E)이다.
(V는 정점의 개수, E는 간선의 개수)
2. 인접행렬
인접행렬이란, matrix를 이용해서 그래프를 표현하는 방법이다.
|V| * |V| 크기의 matrix를 선언한 뒤(|V|는 정점의 개수를 의미)
간선 (i,j)가 존재하면 matrix[i][j]에 1, 존재하지 않으면 0을 넣어준다.
|V| * |V| 크기의 matrix를 선언하므로 공간복잡도는 Θ(V^2)이다.
3. 인접리스트와 인접행렬의 비교
<Storage>
- 만약 그래프에 간선이 드문드문 존재한다면, 인접리스트가 낫다. (|E| < |V|^2 이기 때문)
- 만약 그래프에 간선이 빽빽히 존재한다면, 인접행렬이 낫다. (인접행렬은 한 entry에 대해 하나의 비트(0 or 1)만 사용하기 때문)
<간선(i,j)가 존재하는지 확인하기 위한 시간복잡도>
- 인접리스트: O(V)
- 인접행렬: Θ(1)
필요한 개념은 계속 추가할 예정!
'Algorithm > 이론' 카테고리의 다른 글
| [알고리즘] 비트연산자, 비트마스킹 (0) | 2020.03.28 |
|---|---|
| [알고리즘] Linked List(연결 리스트) (0) | 2020.03.11 |