1. 그래프 기초
Node와 Edge로 구성된 집합
노드는 데이터를 표현하는 단위, 에지는 노드 사이의 연결을 의미합니다.
그래프 종류는 다음과 같습니다.
- 유니온 파인드: 사이클 유무를 판단하는 데 사용
- 위상 정렬: 사이클이 없고 방향이 없어야 함, 노드 정렬하는데 사용, 결과가 두개 이상 있을 수 있음
- 최소 신장 트리(MST): 그래프에서 최소의 가중치 합으로 모든 노드를 연결
!! 사이클이 없어야 하므로 최소 신장 트리 안에 유니온 파인드를 넣어서 사용합니다.
최단거리 알고리즘
- 다익스트라: 시작점이 있고 음수간선(가중치가 음수인 에지)이 없음
- 벨만-포드: 시작점이 있고 음수간선도 있음
- 플로이드-워셜: 시작점 없고 임의의 모든 노드 쌍의 최단거리를 구함
2. 그래프의 표현
세 가지의 방법으로 가중치가 없고 있는 그래프를 표현하는 방법을 설명합니다.
1) 에지 리스트 (Edge List)
에지를 중심으로 그래프를 표현하며, 배열에 출발 노드와 도착 노드, 가중치를 저장하여 에지를 표현합니다.
가중치가 없는 그래프
: 가중치가 없는 경우, 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개입니다.
: 사진은 방향이 있는 그래프를 예시로 들었으나, 방향이 없는 그래프라면 [1,2]와 [2,1]은 같은 표현입니다.
가중치가 있는 그래프
: 가중치가 있는 경우, 3번째 요소로 가중치가 추가되기 때문에 배열의 행은 3개입니다.
++ 에지 리스트는 구현하기 쉬우나 특정 노드와 관련되어있는 에지를 탐색하기는 쉽지 않습니다.
++ 따라서 벨만 포드나 MST 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않습니다.
2) 인접 행렬 (Adgacency Matrix)
2차원 배열로 그래프를 표현하며, 위와 다르게 노드 중심으로 그래프를 표현합니다.
가중치가 없는 그래프
: 가중치가 없으므로 1을 저장하며, 이는 1에서 2로 향하는 에지가 존재한다는 표시입니다.
가중치가 있는 그래프
: 출발 노드에서 도착 노드로 향하는 에지의 가중치를 해당 배열에 기록합니다.
++ 구현이 쉽고 가중치 값을 배열에 접근하여 바로 확인할 수 있습니다.
++ 하지만 특정 노드와 관련된 에지를 탐색하려면 배열의 열 혹은 행의 수만큼 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어집니다.
++ 노드의 개수가 많은 경우에 2차원 배열을 선언할 수 없을 수도 있습니다.
3) 인접 리스트 (Adjacency List)
ArrayList로 그래프를 표현하며, 노드 개수만큼 ArrayList를 선언합니다.
가중치가 없는 그래프
: 리스트에는 특정 노드와 연결되어있는 노드의 개수 만큼 배열을 연결합니다.
ex) ArrayList[1]에 [2,3]을 연결
가중치가 있는 그래프
: 가중치가 있는경우 자료형을 클래스로 사용합니다.
ex) 도착 노드, 가중치를 갖는 Node 클래스 선언하여 사용
++ 구현이 복잡한 편이지만 노드와 연결된 에지를 탐색하는 시간이 매우 뛰어납니다.
++ 노드 개수가 많아도 공간 효율이 좋습니다.
참고 교재: Do it! 알고리즘 코딩테스트 with JAVA
사진 출처
10 Graph Algorithms Visually Explained
Data Structures 101: Graphs — A Visual Introduction for Beginners
