graph.md

그래프 관련 알고리즘

작성자 : 서그림, 정희재

Table of Contents

• 다익스트라 알고리즘 (Dijkstra Algorithm)
• 벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm)
• 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
• 분리 집합(Union Find)과 크루스칼(Kruskal) 알고리즘

---

최단 경로 알고리즘

• 작성자 서그림 | 최단 경로 알고리즘

최단 경로 문제

최단 경로 문제란, 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 최단 경로 문제는 다음과 같은 유형들이 있다.

• 단일 출발 (single-source) 최단 경로 : 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는다.
• 단일 도착 (single-destination) 최단 경로 : 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는다.
  (그래프 내의 간선들을 뒤집으면 단일 출발 최단 경로 문제로 바뀔 수 있다.)
• 단일 쌍 (single-pair) 최단 경로 : 어떤 정점 v에서 v'로 가는 최단 경로를 찾는다.
• 전체 쌍 (all-pair) 최단 경로 : 모든 정점 쌍들 사이의 최단 경로를 찾는다.

최단 경로 문제를 해결하는 알고리즘으로는 대표적으로 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 있다. 각 알고리즘을 적용하기 적합한 유형은 다음과 같다.

• 다익스트라 알고리즘 : 음이 아닌 가중 그래프에서의 단일 출발, 단일 도착, 단일 쌍 최단 경로 문제
• 벨만-포드 알고리즘 : 가중 그래프에서의 단일 출발, 단일 도착, 단일 쌍 최단 경로 문제
• 플로이드-워셜 알고리즘 : 전체 쌍 최단 경로 문제
• BFS : 가중치가 없거나 가중치가 동일한 그래프에서 최단 경로를 찾는 경우 가장 빠르다.

다익스트라 알고리즘 (Dijkstra Algorithm)

그래프 G = (V, E) 에서 특정 출발 정점(S)에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 음의 가중치를 가지는 간선이 없을 때 정상적으로 동작한다.

알고리즘 설계 및 구현

1. 출발 노드 S를 설정한다.
2. 출발 노드 S에서 모든 노드들까지의 최단 거리를 저장하는 배열 D를 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. (D 배열 검사)
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 배열 D를 갱신한다.
5. 모든 노드를 방문할 때까지 3, 4 과정을 반복한다.

다익스트라 알고리즘 구현 ▶️ DijkstraTest.java

특징

• 각 정점을 최대 한 번씩만 방문하여 최단 거리를 확정한다.
• 아직 방문하지 않은 정점들 중 최단 거리인 정점을 찾아 방문하는 식으로 진행된다.
  • 이 때, 최단 거리가 최소인 정점을 찾는 과정에서 PriorityQueue 또는 Heap 자료구조를 이용하면 더욱 개선된 알고리즘이 가능하다.
• 매 순간마다 최단 거리의 정점을 선택하는 과정을 반복하므로 그리디 알고리즘으로 분류된다.
• 총 V x V 번 연산이 필요하므로 O(V^2) 의 시간복잡도를 가진다.

개선된 다익스트라 알고리즘

다익스트라 알고리즘에는 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는 과정이 있다. 이 과정에서 다음과 같은 비용이 발생한다.

• 방문했는지 여부에 대한 정보를 저장하는 배열을 노드의 크기(V) 만큼 생성하고 접근해야 한다.
• D 배열을 모두 순회하여 최단 거리가 짧은 노드를 선택해야 한다.

이 과정을 PriorityQueue 또는 Heap 자료구조를 이용하면 노드를 선택하는 비용을 O(V)에서 O(log{힙에 저장한 정점의 개수})로 줄일 수 있다. 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용하면 되며, 힙을 통해 구현된 Priority Queue를 사용해도 좋다. 동작 과정은 다음과 같다.

1. 출발점에 대하여 D 배열을 초기화할 때 D[S] = 0을 해준다. 이와 동시에 힙에 노드 정보(번호, 거리 : [S, 0])를 넣어준다.
2. 힙에서 맨 위에 있는 노드 I를 꺼낸다.
3. 만일 꺼낸 노드 I의 거리 정보가 현재 D[I]보다 크다면 이미 방문한 노드일 것이므로 무시한다.
4. I를 대상으로 다익스트라 알고리즘을 수행하는데, D 배열이 갱신될 경우 그 노드 정보를 힙에 넣는다.
   (D[J] = D[I] + W 로 갱신될 경우 힙에 노드 J([J, D[J]])를 삽입한다.)
5. 힙에 노드가 없을 때까지 반복한다.

개선된 다익스트라 알고리즘의 시간 복잡도는 O(ElogV) 이다. (O(ElogE) → O(ElogV²) → O(2ElogV) → O(ElogV))

개선된 다익스트라 알고리즘 구현 ▶️ DijkstraTest.java > class ImprovedDijkstra

벨만-포드 알고리즘 (Bellman-Ford-Moore Algorithm)

그래프 G = (V, E) 에서 특정 출발 정점(S)에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘과 달리, 음의 가중치를 가지는 간선도 가능하다.

아이디어

• 가중 그래프 (V, E)에서 어떤 정점 A에서 정점 B까지의 최단 거리는 최대 V - 1개의 간선을 사용한다. (= 시작 정점 A를 포함하여 최대 V개의 정점을 지난다.)

알고리즘 설계 및 구현

1. 출발 노드 S를 설정한다.
2. 출발 노드 S에서 모든 노드들까지의 최단 거리를 저장하는 배열 D를 초기화한다.
3. 그래프의 모든 간선을 돌면서 각 노드로 가는 비용을 계산하여 최단 거리 배열 D를 갱신한다.
4. 3 과정을 (노드의 개수 - 1)번, 즉 V-1번 반복한다.
5. 3 과정을 한 번 더 반복하였을 때, 배열 D가 갱신되면 음의 사이클이 있는 것으로 판단한다.

벨만-포드 알고리즘 구현 ▶️ BellmanFordTest.java

특징

• 음의 가중치를 가지는 간선도 가능하므로, 음의 사이클의 존재 여부를 따져야 한다.
• 최단 거리를 구하기 위해서 V - 1번 E개의 모든 간선을 확인한다.
• 음의 사이클 존재 여부를 확인하기 위해서 한 번 더 (V번째) E개의 간선을 확인한다. 이 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가진다.
• 따라서 총 V x E 번 연산하므로 O(VE) 의 시간복잡도를 가진다.

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

그래프 G = (V, E) 에서 모든 정점 사이의 최단 경로를 구하는 알고리즘이다.

아이디어

• 어떤 두 정점 사이의 최단 경로는 어떤 경유지(K)를 거치거나, 거치지 않는 경로 중 하나이다. 즉 정점 A와 정점 B 사이의 최단 경로는 A-B 이거나 A-K-B 이다.
• 만약 경유지(K)를 거친다면 최단 경로를 이루는 부분 경로 역시 최단 경로이다. 즉 A-B의 최단 경로가 A-K-B라면 A-K와 K-B도 각각 최단 경로이다.

알고리즘 설계 및 구현

1. 각 노드들 사이의 최단 거리를 저장하는 2차원 배열 D를 초기화한다.
2. 각 노드가 경유지 K를 지날 때마다 최단 경로를 계산하여 배열 D를 갱신한다.
3. 동적 계획법으로 해결하며, 점화식은 D[A][B] = min(D[A][B], D[A][K] + D[K][B] 이다.

플로이드-워셜 알고리즘 구현 ▶️ FloydWarshallTest.java

특징

• 사이클이 없다면 음수 가중치를 가져도 적용 가능하다.
• 동적 계획법(Dynamic Programming)으로 접근한다.
• 모든 가능한 경유지에 대해서 모든 정점 -> 모든 정점으로 가는 최단 거리를 확인하므로 연산 횟수는 V^3이고, 따라서 시간복잡도는 O(V^3) 이다.

---

분리 집합(Union Find)과 크루스칼(Kruskal) 알고리즘

스터디 자료 - 작성자 정희재 | Union Find & Kruskal Algorithm

서로소 집합(Disjoint Set)과 Union-Find

서로소 집합(Disjoint Set)은 교집합이 없는, 즉 공통되는 원소가 없는 집합을 말한다. Union-Find는 서로소 집합을 표현할 때 사용되는 알고리즘으로, 서로소 집합의 정보를 확인(Find)하고 조작(Union)한다. Union Find 알고리즘을 이용하면 서로 다른 두 노드가 같은 집합 내에 속해 있는지 확인할 수 있다.

Union Find 구현

초기화 (initialize)

root 배열에 i 원소의 부모 노드 번호를 저장한다. i 원소가 루트 노드라면, 자기 자신의 번호를 저장한다.

void initialize() {
    for (int i = 1; i <= N; i++) {
        root[i] = i;
    }
}

n번 노드의 root 노드 번호 찾기 (find)

int find(int n) {
    if (root[n] == n) return n;
    return root[n] = find(root[n]);
}

a 노드와 b 노드를 같은 집합으로 묶기 (merge, union)

void merge(int a, int b) {
    root[find(b)] = find(a);
}

Union Find를 활용한 MST 찾기 - Kruskal Algorithm

무향 그래프 G가 순환이 없는 연결 그래프이면 그래프 G는 트리(Tree)이다.

신장 트리 (Spanning Tree)란 무향 연결 그래프 G의 부분 그래프이며, G의 모든 정점을 포함하는 트리(Tree)인 그래프이다.

여기서 최소 신장 트리 (Minimum Spanning Tree, MST)란 무향 연결 그래프 G에서 간선의 가중치의 합이 최소인 신장 트리이다. 이 최소 신장 트리 MST를 구할 수 있는 알고리즘으로는 크루스칼 알고리즘, 프림 알고리즘이 있다. 그 중 프림 알고리즘은 크루스칼 알고리즘에 비해 느리고 잘 안 쓰이므로 크루스칼 알고리즘에 대해 알아보겠다. 크루스칼 알고리즘은 Union-Find를 사용해 구현할 수 있다.

Kruskal Algorithm 구현

1. (Cost, A, B) 리스트를 만들어서 모든 간선들의 정보를 Priority Queue에 저장한다. (최소 힙)
2. Priority Queue에서 하나씩 pop하면서 만약 A와 B가 연결되어 있지 않다면 A와 B를 연결하고 전체 비용에 Cost를 더한다.
3. 만일 A와 B가 연결되어 있다면 무시한다.

굵은 글씨 부분을 Union-Find로 구현한다.

시간 복잡도 (E: 간선의 개수) :

Kruskal 알고리즘 구현 ▶️ KruskalTest.java