| # | 도전 과제 | 통과 |
|---|---|---|
| 1 | 그래프와 인접 행렬 | |
| 2 | 그래프와 인접 리스트 |
준비중..
09 그래프
# 그래프
## 목차
1. 그래프란
2. 장점 및 활용
3. 분류
4. 구현
## 1. 그래프란
그래프란, 정점(vertex)과 간선(edge)으로 이루어진 자료구조이다.
## 2. 장점 및 활용
그래프는 객체와 객체 간 관계를 나타냄에 있어 특화되어있다.
이로 인해 실생활의 다양한 분야에서 사용된다. 예를 들면 페이스북의 친구 관계도, 소개팅 매칭 관계도, 지하철역과 연결된 선로 등을 그래프로 표현할 수 있다.
## 3. 분류
그래프는 간선에 대한 방향성과 가중치의 유무에 따라 총 4가지로 분류된다.
## 4. 구현
그래프는 다양한 방법의 구현이 가능하다. 여기서는 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)의 형태로 연습해보자.
#### 1) 인접 행렬
인접 행렬은 2차원 배열로 구현한다. 이 배열을 A라 할 때, 그래프의 정점 0이 1로 연결되었다면, `A[0][1] = 1` 이다. 무방향 그래프의 경우 1또한 0으로 연결된 것이므로 `A[1][0] = 1`이다. 연결되지 않은 경우는 0을 대입한다.
연결의 시작점을 `start`, 도착점을 `end`로 할 때, 위 내용을 일반화하면 다음과 같다.
$$
\begin{align}
A[start][end] &= 1 \text{ (연결) }\\\
A[start][end] &= 0 \text{ (미연결) }
\end{align}
$$
#### 2) 인접 리스트
인접 리스트는 연결 리스트의 배열로 구현한다. 이 배열을 A라 할 때, A[i]는 정점 i에 연결된 모든 노드의 리스트이다.
Challenge
개념 실습! 학습 내용을 진짜 내 것으로 만들기!