그래프 (Graph)

그래프는 트리와 비슷하게 생긴 자료구조로 정점과 간선으로 이루어져있다.

먼저 용어정리를 하자면 정점(Node, Vertex)은 각각의 자료를 말한다.

정점과 정점을 잇는 선을 간선(Edge)라고 한다.

차수(Degree)는 한 정점에 몇 개의 간선이 연결되어 있는가라는 것인데, 위의 사진에서 보면

정점 2의 차수는 4라는 것을 알 수 있다.

자기 자신으로 다시 돌아올 수 있는 경로를 사이클(Cycle)이라고 한다.

그래프는 사람과 사람을 연결해주는 네트워크에서 볼 수 있는 구조이기도 하고,

지하철 노선도 역시 그래프로 해석할 수 있기 때문에, 현실의 많은 것들과

연관이 되어있기 때문에 중요한 자료구조라고 할 수 있다.

그러므로 수학적 정리가 매우 방대하고, 스택과 큐 같은 자료구조는 구현이 간단하지만

그래프는 그만큼 이론과 구현이 어렵다고 볼 수 있다.

그래프와 관련된 중요한 수학적 지식이 몇가지 있는데 첫번 째는 간선의 개수는 정점의 제곱보다 작거나 같다는 것이다.

왜냐하면 정점이 4개 있는데, 이중에 2개를 선택하는 경우의 수는 n(n-1)/2 인데, 이것은 정점 n의 제곱보다

무조건 작거나 같기 때문이다. 위의 사진만 봐도 쉽게 이해 할 수 있다.

두번 째로 각각의 정점의 차수의 합은 간선의 개수의 2배라는 것인데, 차수의 합을 구할 때

각 간선을 두 번씩 세기 때문에 이러한 공식을 도출할 수 있다.

---

그래프를 구현하는 방법은 2가지가 있는데, 그 중에 첫번 째는 2차원 인접행렬을 이용하여 구현하는 것이다.

정점과 정점이 연결되어있으면 1로 표시하고, 연결되어 있지 않으면 0으로 표시한다.

그래프에서는 보통 두 가지를 물어볼 수 있다.

Q1. x와 y가 연결 돼있는가?

Q2. x와 연결된 정점이 모두 무엇인가?

2차원 배열을 이용하여 그래프를 구현하면 Q1 처럼 x와 y가 연결 돼어 있는가를 배열의 인덱스를 통하여

바로 한번에 알 수 있기 때문에 시간복잡도 O(1)의 속도로 빠르게 연결돼 있는지 안돼있는지 알 수 있다.

하지만 Q2 처럼 정점 x와 연결된 정점을 구할 때에는 한 열의 모든 인덱스를 봐야 하기 때문에,

한번 탐색을 하면 O(n)의 시간이 걸린다.

인접행렬로 구현하면 간선의 개수와 상관없이 2차원 배열을 사용해야 하는 것도 단점이다.

100개의 정점을 가진 그래프가 200개의 간선만 있는 경우 2차원 배열로 구현하면 10000개의 공간이 필요한데,

이 중에 200개의 간선만 1로 표현되기 때문에 나머지 99600개의 공간은 낭비되게 된다.

---

그래프를 구현하는 2번 째 방법인 인접리스트가 있다.

인접리스트는 위의 사진처럼 각 정점에 대하여 인접한 정점의 번호만을 저장한다.

여기서 예시처럼 정점 6개의 그래프를 만들려면 6x4의 2차원 배열이 필요할 수 있다고 생각한다.

하지만 Vector 라는 라이브러리를 이용하여 구현하면 각각의 정점에 필요한 길이만큼의 공간을 할당하여 구현할 수 있다.

Vector를 사용하여 구현한 인접리스트 그래프의 단점은 Q1. x와 y가 연결 돼있는가를 볼 때,

x에 연결돼어 있는 정점을 모두 찾아야하기 때문에 O(deg(v)) 의 시간이 걸린다.

deg(v)라는 것은 v 정점의 차수(degree)라는 뜻이다.

하지만 인접행렬로 구하는 그래프와 다르게 Q2 인접한 정점을 모두 찾는데

Vector를 이용하여 할당되어 있기 때문에  필요한 만큼만 볼 수 있고,

공간을 효율적으로 활용할 수 있다.

출처 : Algorithm LABS