Graph
이번엔 그래프에 대해서 알아보도록 하겠다.
Introduction
일련의
정점(node, vertex, 꼭짓점)집합 V와간선(edge, 변)집합 E로 구성된 자료구조의 일종이다. 일반적으로정점엔 데이터,간선엔 정점과 정잠 사이의 관계 정보가포함되어 있다.
여기서 []는 정점이다([V1]). 정점 사이에는 간선이다(e1).
[V1] ------ e1 ------- [V2]------e3------[V4]
|
[V3] ---- e2---- |
|
e4
|
[V5]
G = (V, E)
V = {V1, V2, V3, V4, V5}
E = {E1, E2, E3, E4}
e1 = (V1, V2)
e2 = (V2, V3)
e3 = (V2, V4)
e4 = (V3, V5)
쉽게 한 마디로 말하면 사물들 간의 순서 또는 관계를 그래프로 표현한 것이라고 생각하면 된다.
그래프는 방향이 있고 없고에 따라서 다음과 같이 나뉘게 된다.
- 유향 그래프 : 그래프에 방향이 있는 그래프
- 무향 그래프 : 그래프에 방향이 없는 그래프 (양방향)
그리고 만약 간선에 가중치가 존재할 시 가중치 그래프 라고 불리게 된다.
- 차수(degree) : 해당 정점에 연결된 간선의 개수(혹은 간선 가중치의 합)
- 인접(adjacent) : 임의의 두 정점이 하나의 간선에 연결돼 있을 때, 서로 인접한다고 한다.
자료구조
인접행렬
위에 있는 그래프를 인접행렬로 표현한다면 다음과 같이 표현된다. j i 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0
i는 기준이 되는 정점, j는 연결되어 있는 정점들이라고 생각하면 된다.
다음의 자료구조를 구현하기 위해서는 2중배열을 사용하면 되는데 구현 방법은 인접리스트에 비해 쉽지만, 인접리스트보다 느릴 수 있다. 이 부분에 대해서는 인접리스트에 대해서 알아보고 이야기하도록 하자.
인접리스트
i j [1] ---> [2] [2] ---> [1] -> [3] -> [4] [3] ---> [2] -> [5] [4] ---> [2] [5] ---> [3]
다음과 같이 표현할 수 있다. 이 부분은 자바로 구현한다면 List<>, C++ 이라면 vector<> 로 구현하면 된다.
참고로 위에서 표현한 것은 가중치는 없다고 하고 표현한 것이다.
인접리스트 > 인접행렬
인접리스트는 인접행렬보다 빠를 가능성이 더 크다. 인접리스트의 경우 실제로 연결되어 있는 정점들만 리스트에 담으면 되지만, 인접행렬의 경우 실제로 연결되어 있지 않아도 배열에 담아야 하기 때문이다.
그래서 만약 출력을 한다고 생각하면, 각각 다음과 같은 코드를 작성할 수 있다.
// 인접행렬
for(int i = 0; i < 5(배열 길이); ++i) {
for(int q = 0; q < 5(배열길이); ++q) {
// 무조건 배열의 길이 끝까지 읽어야 한다.
}
}
// 인접리스트
for(int i = 0; i < arr.length; ++i) {
for(int q=0; q < arr.get(i).length; ++q) {
// arr.get(i) 에 대한 길이만 읽으면 된다.
}
}
즉, 인접행렬은 최악이든 최선이든 무조건 배열 길이 끝까지 읽어야 하지만 인접리스트는 최악일 땐 배열 끝까지 읽겠지만 최선일 경우 하나만 읽을 수도 있다는 것이다.
아래의 코드는 간단하게 이해하기 위해서 작성한 코드이다.
public class Main {
/**
* [V1] ------ e1 ------- [V2]------e3------[V4]
* |
* [V3] ---- e2---- |
* |
* e4
* |
* [V5]
*/
static final int VERTEX = 5;
public static void main(String[] args) {
List<List<Integer>> arr = new ArrayList<>();
for(int i = 0; i < VERTEX; ++i) {
arr.add(new ArrayList<>());
}
arr.get(0).add(1);
arr.get(1).add(0);
arr.get(1).add(2);
arr.get(1).add(3);
arr.get(2).add(1);
arr.get(2).add(4);
arr.get(3).add(1);
arr.get(4).add(2);
for(int i = 0; i < VERTEX; ++i) {
for(int q=0; q < arr.get(i).size(); ++q) {
System.out.print(arr.get(i).get(q) + " ");
}
System.out.println();
}
}
}
출력값 :
1
0 2 3
1 4
1
2
[1] ---> [2]
[2] ---> [1] -> [3] -> [4]
[3] ---> [2] -> [5]
[4] ---> [2]
[5] ---> [3]
출력값에 1씩만 더 한다고 생각하면 된다