1. Graph의 정의
'그래프는 Node와 edge로 구성된 집합이다'
- Node: 데이터를 표현하는 단위
- Edge: Node를 연결
- 가중치(Weight): 에지에 부여된 숫자값
- Tree 또한 그래프의 일종
Grpah Algorithm에는 특징적으로 다음과 같은 세부 알고리즘들이 존재한다
- Union-Find: 노드들이 같은 그룹에 속해 있는지 확인할 때 사용, 싸이클 유무 판단
- 위상 정렬(Topological sort): 선후 관계가 있는 작업들에 유용, 비순환 그래프의 노드들을 순서대로 정렬하는 알고리즘
- 다익스트라(Dijkstra): 단일 출발점에서 모든 node까지의 최단 거리 계산, 간선 가중치가 음수가 없을 때 사용
- 벨만-포드(Bellman-Ford): 다익스트라와 유사하지만, 음수 가중치 허용
- 플로이드 워셜(Floyd-Warshall): 시작점이 없는, 모든 정점 쌍 간의 최단 거리 계산, DP 방식으로 구현
- 최소 신장 트리(MST, Minimum Spanning Tree): 모든 노드를 최소 비용으로(최소 가중치 합으로) 연결하는 트리 구성
2. Graph의 표현
그래프를 구현하는 3가지 방법
1. 에지 리스트
2. 인접 행렬
3. 인접 리스트
1. 에지 리스트
에지 리스트는 '에지'를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현하며, 필요한 경우에 가중치도 저장하여 가중치가 있는 에지를 표현한다.
-
가중치 없는 그래프 표현
가중치가 없는 경우에는 출발점과 도착점만 표현하면 되므로, 배열의 행은 2개면 충분하다. 예를 들면 1에서 2로 가는 에지는 [1,2]로 표현 가능하다. 주의해야할 부분은, 방향이 없는 그래프일 경우, [1,2],[2,1] 두 배열 모두 리스트에 넣어 방향이 없는 경우를 표현해줘야 한다. -
가중치 있는 그래프 표현
행을 3개로 늘려 3번째 행에 가중치를 저장해주면 된다.
에지 리스트는 구현하기는 쉽지만, 특정 노드와 관련된 에지를 탐색하기에는 높은 시간 복잡도가 부여되는 문제가 있어, 이런 문제를 해결하기 위해 벨만 포드나 크루스칼과 같은 알고리즘을 활용한다.
2. 인접 행렬(Adjacency matrix)
인접 행렬은 2차원 배열을 이용하여 그래프를 표현한다. 노드가 N개인 경우, N*N배열을 형성해 그래프를 표현한다.
-
가중치 없는 그래프 표현
위의 그림과 같이 가중치가 없으므로 1을 저장하여 특정 노드에서 특정 노드로 향하는 에지가 있음을 표현한다. -
가중치 있는 그래프 표현
위의 행렬 형태에서 가중치를 넣어주면 된다.
인접 행렬 또한 에지 리스트처럼 구현은 쉽다. 하지만 인접 행렬 역시 특정 에지를 탐색하려면 N번 접근해야 한다는, 노드 개수에 비해 에지가 적을 때 시간 복잡도 면에서 확실한 단점이 존재한다. 또한 N*N배열을 형성해야 하기 때문에 공간 효율성 또한 떨어진다. 따라서 경우에 따라 이를 적절히 활용하는 능력이 필요하다.
3. 인접 리스트(ArrayList)
ArrayList를 활용하여 그래프를 표현한다. 실제 그래프를 표현하는데 있어 제일 많이 사용하는 방식이다.
-
가중치 없는 그래프 표현
인접 리스트가 그래프 표현에 있어서 제일 많이 사용되는 이유가 바로 드러난다. 인접 리스트는 가변적인 자료구조이므로, 해당 이미지에서 1 리스트와 연결된 리스트의 요소 개수를 언제든 늘릴 수 있기 때문에, 그래프를 표현하기에 효과적이다. -
가중치 있는 그래프 표현
가중치가 있는 경우에는 다음과 같이 Node 클래스를 선언하여 활용한다.
인접 리스트를 이용한 그래프 구현은 복잡한 편이지만, 에지를 탐색하는 시간이 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다. 따라서 보통의 코테에서는 인접 리스트를 가장 많이 활용한다.
