Graph

그래프는 정점(Vertex = node)과 간선(Edge)으로 이루어진 추상적인 자료구조(ADT)이다.

정점은 데이터를 나타내며, 간선은 두 정점을 연결한다. 간선은 방향이 있는 경우도 있고, 없는 경우도 있다. 방향이 없는 그래프에서 간선은 무방향(undirected) 간선이라고 부르고, 방향이 있는 그래프에서는 방향(directed) 간선이라고 부릅니다. 또한 무방향 간선은 양방향 간선으로 간주해도 된다.

그래프의 종류

1. 무방향 그래프

   두 정점을 연결하는 간선에 방향이 없는 그래프이다.
   무방향 그래프에서 정점 A와 B를 연결하는 간선은 (A, B)로 표현하는데 (A, B)와 (B, A)는 같은 간선을 나타낸다.

2. 방향 그래프

   간선에 방향이 있는 그래프이다.

3. 완전 그래프

   한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프이다.

4. 가중 그래프

   정점을 연결하는 간선에 가중치를 할당한 그래프이다.

5. 유향 비순환 그래프

   방향 그래프에서 사이클이 없는 그래프이다.

6. 연결 그래프

   떨어져 있는 정점이 없는 그래프이다.

7. 단절 그래프

   서로 떨어져 있는 정점의 집합이 존재하는 그래프이다.

그래프의 구현

인접 행렬

정점을 행과 열로 구성한 N x N 행렬을 이용하여 그래프를 표현한다. 각 행과 열은 정점을 나타내고, 간선이 존재하면 1, 존재하지 않으면 0으로 표시한다.

인접 리스트

각 정점에 인접한 정점들을 리스트나 배열로 저장한다. 이를 위해 리스트나 배열의 인덱스는 정점을 나타내며, 해당 인덱스에 저장된 리스트나 배열은 해당 정점에 인접한 정점들을 나타낸다.

인접 행렬 vs 인접 리스트

정점의 수를 V라 하면, 인접 행렬로 구현할 때 최악의 시간복잡도는 O(V^2)이다. 2차원 행렬로 구현되기 때문이다. 그에 반해 인접 리스트는 LinkedList로 구현되기 떄문에 최악의 시간복잡도가 O(E)이다. 그러나 LinkedList로 구현할 경우 시간이 오래 걸리고 디버그가 어렵기 때문에 Java의 경우엔 ArrayList를 사용해 구현한다.

그래프의 활용

그래프는 다양한 분야에서 활용된다. 지도나 도로망을 그래프로 표현하고, 경로 탐색 알고리즘을 이용해 최단 경로를 찾을 수 있다. 또한 컴퓨터 네트워크에서 구성을 분석하거나, 알고리즘 분석에서 중요한 역할을 한다.