그래프
그래프는 노드와 에지로 구성된 집합.
노드는 데이터를 표현하는 단위이고 에지는 노드를 연결.
에지 리스트
에지 리스트(edge list)는 에지를 중심으로 그래프를 표현.
배열에 출발 노드, 도착 노드를 저장하여 에지를 표현. arr[2][N]
또는, 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현. arr[3][N]
가중치 없는 그래프 표현
- 1, 2
- 1, 3
- 3, 4
- 2, 4
- 2, 5
- 4, 5
인접 행렬
인접 행렬(adjacency matrix)은 2차원 배열을 자료구조로 이용하여 그래프를 표현.
에지 리스트와 다르게 노드 중심으로 그래프를 표현.
a에서 b를 향하는 에지를 인접 행렬은 a행 b열에 1을 저장하는 방식으로 표현.
*인접 리스트
인접 리스트(adjacency list)는 ArrayList로 그래프를 표현.
노드 개수만큼 ArrayList를 선언.
ArrayList<Integer>[N]
- 1 -> 2,3
- 2 -> 4,5
- 3 -> 4
- 4 -> 5
- 5
그래프를 구현하는 다른 방법에 비해 인접 리스트를 이용한 그래프 구현은 복잡한 편.
하지만, 노드가 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며,
노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않음.
이런 장점으로 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호.
유니온 파인드
유니온 파인드(Union-find)는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산으로 구성된 알고리즘.
- union 연산
- 각 노드가 속합 집합을 1개로 합치는 연산.
- find 연산
- 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산.
- 일반적으로 1차월 배열을 사용한다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화.
- union(a, b) 연산일 때 arr[b] = a 로 변경하여 대표 노드를 설정한다. b의 대표노드가 a가 되는 것.
- 이때, arr[x] = x 가 아니라면 대표노드가 아니므로 대표노드를 찾아서(find 연산) 설정한다.
- 대표 노드를 찾는 과정은 재귀로 구현하게 된다.
- 대표 노드를 찾게 되면 재귀를 빠져 나오면서 거쳐왔던 모든 노드 값을 대표 노드로 설정한다.
// 초기 대표노드 설정
for (int i = 0; i < n; i++) {
arr[i] = i;
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (b != a) arr[b] = a; // a와 b가 같은 집합이 아니라면 연결
}
private static int find(int x) {
if (arr[x] == x) return x; // 대표 노드 반환
else return arr[x] = find(arr[x]); // 대표 노드를 찾아서 설정, 거쳐왔던 모든 노드를 설정
}*코드는 쉽지만 개념은 어려울 수 있으니 반복적으로 보자.
위상 정렬
위상 정렬(Topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘.
- 기능
- 노드 간의 순서를 결정
- 특징
- 사이클이 없어야 함
- 시간 복잡도 (노드 수 : V, 에지 수 : E)
- O(V + E)
위상 정렬은 항상 유일한 값으로 정렬되지 않음.
또한, 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없음.
int[] arr = new int[n]; // 진입 차수 배열
ArrayList<Integer>[] all = new ArrayList[n]; // 사이클 없는 그래프
for (int i = 0; i < n; i++) {
all[i] = new ArrayList<>(); // 초기화
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
all[a].add(b); // 그래프 구성 하면서
arr[b]++; // 진입차수 계산
}
boolean b = true;
while (b) {
b = false;
for (int i = 1; i < n; i++) {
if (arr[i] == 0) {
System.out.println(i); // 진입차수가 0인 배열부터 탐색
arr[i] = -1; // 탐색 끝났으면 -1로 설정
for (int k : all[i]) {
arr[k]--; // 진입차수 계산
}
}
if (arr[i] != -1) {
b = true; // 모든 진입차수 배열이 -1이 될때까지 반복
}
}
}- 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수. ArrayList에 그래프를 구성할 때 진입차수를 계산(1씩 더함)한다.
- 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 출력.
- 인접 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
- 이런식으로 모든 노드를 출력할 때까지 반복한다.
다익스트라
다익스트라(Dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘.
- 기능
- 출발 노드와 모든 노드 간의 최단 거리 탐색
- 특징
- 에지는 모두 양수
- 시간 복잡도(노드 수 : V, 에지 수 : E)
- O(E log V)
int[] distance = new int[n]; // 거리 저장 배열
boolean[] visited = new boolean[n]; // 노드 방문 유무 배열
ArrayList<Edge>[] alArr = new ArrayList[n]; // 그래프를 인접 리스트로 구현
PriorityQueue<Edge> q = new PriorityQueue<>(); // 가장 작은 현재값을 찾기 위한 우선순위 큐
for (int i = 0; i < n; i++) {
alArr[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
distance[i] = MAX_VALUE; // 가장 큰 값으로 초기화
}
// 그래프 값을 입력 받아서 인접 리스트로 구현
for (int i = 0; i < m; i++) {
int index = sc.nextInt();
Edge e = new Edge(sc.nextInt(), sc.nextInt());
alArr[index].add(e);
}
// 시작 노드 0으로 설정
q.add(new Edge(start, 0));
distance[start] = 0;
while (q.isEmpty() == false) {
int node = q.poll().getNode();
if (visited[node]) continue; // 한번 방문한 노드는 다시 연산하지 않음
visited[node] = true;
for (Edge e :
alArr[node]) {
// Min(선택 노드의 최단 거리 배열값 + 에지 가중치, 연결 노드의 최단 거리 배열값)
if (distance[node] + e.getValue() < distance[e.getNode()]) {
// 거리 배열과 우선순위 큐를 동기화 해가며 연산
distance[e.getNode()] = distance[node] + e.getValue();
q.add(new Edge(e.getNode(), distance[e.getNode()]));
}
}
}
class Edge implements Comparable<Edge> {
private int node;
private int value; // 가중치
Edge(int node, int value) {
this.node = node;
this.value = value;
}
public int getNode() {
return node;
}
public int getValue() {
return value;
}
// 우선순위 큐의 정렬 기준
@Override
public int compareTo(Edge o) {
return this.value - o.getValue();
}
}- 인접 리스트로 그래프 구현
- 거리 배열 초기화
- 이때, 출발 노드는 0으로 설정
- 나머지는 가장 큰 값(MAX_VALUE)으로 설정
- 값이 가장 작은 노드 선택
- 이 과정을 쉽게 하기위해서 우선순위 큐를 사용
- 거리 배열과 우선순위 큐를 동기화 해가며 연산을 진행
- 선택된 노드에 연결된 에지의 값을 바탕으로 연결된 다른 노드의 값을 업데이트
- 선택 노드의 최단 거리 배열값 + 에지 가중치
- 연결 노드의 최단 거리 배열 값
- 위 두개의 값 중에서 더 작은 값으로 업데이트
- 모든 노드가 처리될 때까지 반복
- 거리 배열 완성!
벨만-포드
벨만-포드(Bellman-ford-moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘.
- 기능
- 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
- 특징
- 음수 가중치 에지가 있어도 수행할 수 있음
- 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
- 시간 복잡도(노드수 : V, 에지 수 : E)
- O (VE)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 노드 수
int m = sc.nextInt(); // 엣지 수
ArrayList<Edge> al = new ArrayList<>(); // 엣지 정보를 저장할 배열
int[] distance = new int[n + 1]; // 거리 정보를 저장할 배열
Arrays.fill(distance, Integer.MAX_VALUE); // 가장 큰 값으로 초기화
distance[1] = 0; // 출발 노드 설정
for (int i = 0; i < m; i++) {
al.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt())); // 엣지 정보 저장
}
// 벨만-포드 알고리즘
for (int i = 0; i < n - 1; i++) { // n-1 만큼 반복
for (int j = 0; j < m; j++) {
Edge e = al.get(j);
if (distance[e.start] != Integer.MAX_VALUE && distance[e.end] > distance[e.start] + e.value) {
distance[e.end] = distance[e.start] + e.value;
}
}
}
// 음수 사이클 체크, 마지막 n 번째 반복의 의미
boolean b = false;
for (int j = 0; j < m; j++) {
Edge e = al.get(j);
if (distance[e.start] != Integer.MAX_VALUE && distance[e.end] > distance[e.start] + e.value) {
b = true; // 데이터가 갱신된다면 음수 사이클 존재
}
}
if (b == false) {
System.out.println("음수 사이클 존재 하지 않음");
} else {
System.out.println("음수 사이클 존재");
}
}
}
class Edge {
int start;
int end;
int value;
public Edge(int start, int end, int value) {
this.start = start;
this.end = end;
this.value = value;
}
}최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1.
노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문.
음수 사이클 존재를 확인하기 위해서 마지막 N 번째 업데이트를 수행.
이때 업데이트가 된다면 음수 사이클이 있다는 뜻.
음수 사이클이 존재하면 반복을 거치면 거칠 수록 가중치가 계속 감소하므로 최단거리 계산이 불가.
벨만-포드 알리즘을 사용하여 최단 거리를 구하기보다는 음수 사이클을 판별하는 문제가 더 많이 나옴.
(이해하기가 점점 어려워진다.. 일단 외우는 중..)
플로이드-워셜
플로이드-워셜(Floyd-warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘.
- 기능
- 모든 노드 간에 최단 경로 탐색
- 시작점을 지정하지 않음
- 특징
- 음수 가중치 에지가 있어도 수행할 수 있음
- 동적 계획법의 원리를 이용해 알고리즘에 접근
- 시간 복잡도(노드 수 : V)
- O (V^3)
플로이드-워셜 알고리즘의 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt() + 1;
int m = sc.nextInt();
int bigNumber = 10000001; // 충분히 큰 수 설정, MAX_VALUE는 안된다 MAX_VALUE 끼리 연산을 할수도 있기 때문.
int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) arr[i][j] = 0;
else arr[i][j] = bigNumber;
}
}
for (int i = 0; i < m; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
int value = sc.nextInt();
if (arr[start][end] > value) arr[start][end] = value;
}
// 플로이드 워셜 알고리즘 수행
for (int i = 1; i < n; i++) {
for (int s = 1; s < n; s++) {
for (int e = 1; e < n; e++) {
arr[s][e] = Math.min(arr[s][e], arr[s][i] + arr[i][e]);
}
}
}
}
}그래프를 인접 행렬로 표현한 다음 점화식을 적용한다.
출발 노드 S
경유 노드 N
도착 노드 E
에지의 가중치 W
라고 했을 때 점화식은 아래와 같다.
Arr[S][E] = Math.min(Arr[S][E], Arr[S][N] + Arr[N][E])
최소 신장 트리
최소 신장 트리(Minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리.
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1 개다.
최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장.
최소 신장 트리는 다른 그래프 알고리즘과는 달리, 에지 리스트의 형태를 이용해 데이터를 담는다는 특징이 있음.
에지를 기준으로 하는 알고리즘이기 때문.
사이클이 존재하면 안되는 특징이 있기 때문에 사이클 판별 알고리즘은 유니온 파인드 알고리즘을 내부에 구현해야 함.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] arr;
static int result = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 노드 수
int m = sc.nextInt(); // 엣지 수
Edge[] edges = new Edge[m];
arr = new int[n + 1]; // 유니온 파인드 연사을 위한 배열 생성
for (int i = 0; i < n; i++) {
arr[i] = i;
}
for (int i = 0; i < m; i++) {
edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()); // 노드1, 노드2, 가중치
}
Arrays.sort(edges); // 가중치 오름차순 정렬
for (int i = 0; i < m; i++) {
Edge edge = edges[i];
union(edge); // 유니온 파인드 연산
}
System.out.println(result);
}
private static void union(Edge e) {
int node1 = find(e.node1);
int node2 = find(e.node2);
if (node1 != node2) {
arr[node2] = node1; // 같은 부모가 아닐 경우 union
result += e.value; // 이때, 최소 경로값 더해줌
}
}
private static int find(int node1) {
if (arr[node1] == node1) return node1;
else return arr[node1] = find(arr[node1]);
}
}
class Edge implements Comparable<Edge> {
int node1;
int node2;
int value;
public Edge(int node1, int node2, int value) {
this.node1 = node1;
this.node2 = node2;
this.value = value;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
}- 그래프를 에지 리스트로 구현
- 유니온 파인드 배열 초기화
- 에리 리스트의 가중치 오름 차순으로 에지 리스트 정렬
- 가중치가 낮은 에지부터 union 연산
- union 가능한 에지들의 가중치들을 모두 더하여 출력