(0) 그래프란?
a. 정의
값을 담고 있는 정점(Vertex)와 그 정점들을 잇는 간선(Edge)으로 이루어져 있는 자료구조
b. 그래프 관련 용어
| 용어 | 뜻 |
|---|---|
| 정점(Vertex or Node) | 데이터를 저장하는 곳 |
| 간선(Edge) | 정점과 정점을 잇는 선 |
| 인접하다. | 정점 A와 B가 간선으로 이어져 있으면, 정점 A와 B는 서로 인접하다.라고 한다. 인접 정점: 하나의 정점 A와 간선으로 이어져 있는 정점들을 인접정점이라고 한다. 위의 예시에서 B는 A의 인접정점이다. |
| 차수 | 하나의 정점 A와 연결된 간선의 개수이다. a의 예시에서 정점2의 차수는 3이고 정점4의 차수는 4이다. 진입 차수: 방향이 있는 그래프에서 외부로부터 들어오는 간선의 개수를 말한다. 진출 차수: 방향이 있는 그래프에서 외부로 뻗어나가는 간선의 개수를 말한다. |
c. 그래프의 종류
무방향 그래프: 간선에 방향이 없는 그래프
방향 그래프: 간선에 방향이 있는 그래프
가중치 그래프: 간선에 가중치가 있는 그래프
완전 그래프: 모든 정점이 서로 연결된 그래프
사진 출처: 블로그
(1) 인접 행렬
출발정점의 번호를 행, 도착정점의 번호를 열에 저장하여 그래프의 간선을 2차원 배열로 나타내는 방법을 말한다.
가중치가 없는 그래프를 인접 행렬로 구현
: 위의 그림과 같이 1을 저장하여 두 정점 사이에 간선이 있음을 기록한다.
가중치가 있는그래프를 인접 행렬로 구현
: [출발 정점] [도착 정점] = 가중치 형태로 인접행렬의 값으로 가중치를 저장한다.
인접 행렬로 구현해서 문제를 풀었을 때 문제점
: 간선의 개수가 적은 경우 메모리 낭비가 심하다. -> 인접 리스트의 경우 간선이 있는 경우에만 표현하기 때문에 대부분 문제에서는 인접 리스트를 사용한다.
출처: 블로그
(2) 인접 리스트
a. 가중치가 없는 그래프의 인접 리스트
ArrayList<Integer> [] lists = new ArrayList [N];
lists["출발정점"].add("도착정점");Integer형 ArrayList 배열을 만든다.
원소 하나 하나가 출발정점을 의미하고 원소 안의 List의 값들은 출발 정점에서 갈 수 있는 정점들이 저장되어 있다.
b. 가중치가 있는 그래프의 인접 리스트
ArrayList<int[]> lists = new ArrayList [ N + 1 ];
lists["출발 정점"].add(new int[]{"도착 정점", "가중치"});ArrayList의 자료형을 int[] 로 바꿔서 가중치 또한 저장할 수 있도록 바꾼다. 배열 대신 도착정점과 가중치를 담은 Class를 이용하여 문제를 풀어도 된다.
3. 간선 리스트
그냥 (출발정점, 도착정점, 둘 사이 간선의 가중치) 형태로 나타내기만 하면 된다. 열이 3개인 2차원 배열을 이용해도 되고, 배열 3개를 나눠 구현해도 된다.
int [] start_vertex = new int [N + 1];
int [] end_vertex = new int [N + 1];
int [] edge_weight = new int [N + 1];
