> For the complete documentation index, see [llms.txt](https://koalas-organization.gitbook.io/koala_codingtest_study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koalas-organization.gitbook.io/koala_codingtest_study/graph.md).
# 그래프
연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조
그래프는 우리에게 매우 친근합니다. 고등학교 때 데이터를 정리해 놓을 때나, 마인드맵을 그려가면서 공부할 때, 모두 유용하게 사용하였는데요. 우리는 어떻게 컴퓨터에게 그래프의 개념을 설명해줄 수 있을지 알아봅시다.
먼저 그래프의 특징에 대해 알아봅시다.
정점(V, vertex)과 간선(E, edge)
그래프는 정점과 간선으로 이루어져 있습니다. 위 그림에서 볼 수 있듯이,
* vertex는 정점 또는 노드라고 말하며, 여러 가지 특성을 가질 수 있는 객체를 의미합니다.
* edge는 간선 또는 link라고 말하며 정점들 간의 관계를 의미합니다.
그래프의 종류는 크게 두 개로 나뉩니다.
차례대로 유향 그래프, 무향 그래프입니다.
그림으로 볼 수 있듯이 유향그래프는 방향이 존재하고, 무향그래프는 방향이 존재하지 않습니다.\
노드 간 이동 시 유향 그래프에서는 해당 방향으로만 이동 가능하고, 무향그래프에서는 자유롭게 이동할 수 있다는 특징이 있습니다.
이번에는그래프를 나타내는 두 가지 표현 방법을 알아봅시다.
📌인접행렬
인접행렬이란 이름 그대로 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미합니다.
위 무향그래프를 보면 노드0에서 노드3으로 이동할 수 있으므로 (0,3) 값을 1로 할당하였습니다. \
0에서 2처럼 이동할 수 없는 경우에는 0으로 할당합니다.
\
📌인접리스트
그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방식을 의미합니다.\
파이썬에서는 dictionary로 구현하거나 또는 이차원 배열에 append하는 방식으로 구현할 수 있습니다.
위 그래프에서 우리는 노드 0에서는 노드 1,2,3으로 갈 수 있음을 알 수 있습니다.\
인접리스트 방법은 인접 행렬 방법보다 공간적 측면에서 낭비가 없어 효율적입니다.
아래와 같이 표현 가능합니다.
```python
graph = { 0: [1,2,3],
1: [0,2],
2: [0,1,3],
3: [0,2] }
graph = [[1,2,3], [0,2], [0,1,3], [0,2]]
```
