자료구조 with 자바

준비중..

자료구조 with 자바

데이터를 효율적으로!

09 그래프

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

Challenge

개념 실습! 학습 내용을 진짜 내 것으로 만들기!