5장: 알고리즘에서의 그래프
그래프는 객체 간의 연결과 관계를 모델링하는 기본적인 데이터 구조입니다. 사회 네트워크와 웹 페이지 링크 모델링, 교통, 스케줄링, 자원 할당 문제 해결 등 컴퓨터 과학 및 다양한 분야에서 광범위하게 활용됩니다. 이 장에서는 무방향 그래프, 깊이 우선 탐색, 너비 우선 탐색, 최소 신장 트리, 최단 경로 등 그래프 작업을 위한 기본 속성과 알고리즘을 탐구합니다.
무방향 그래프
무방향 그래프는 정점(노드)들이 간선으로 연결된 집합입니다. 정식으로 정의하면, 무방향 그래프 G는 정점 집합 V와 정점 쌍 집합 E로 구성된 쌍(V, E)입니다. 간선 (v, w)는 정점 v와 w를 연결합니다. 이때 v와 w는 인접하거나 이웃이라고 합니다. 정점의 차수는 해당 정점에 연결된 간선의 수입니다.
다음은 간단한 무방향 그래프의 예시입니다:
A --- B
/ / \
/ / \
C --- D --- E이 그래프에서 정점 집합 V = {A, B, C, D, E}이고, 간선 집합 E = {(A, B), (A, C), (B, D), (B, E), (C, D), (D, E)}입니다.
프로그램에서 그래프를 표현하는 방법은 여러 가지가 있습니다. 두 가지 일반적인 방법은 다음과 같습니다:
-
인접 행렬: n x n 크기의 부울 행렬 A, 여기서 n은 정점의 수입니다. 행렬 원소 A[i][j]가 참이면 정점 i에서 정점 j로 간선이 존재함을 나타냅니다.
-
인접 리스트: 크기 n의 배열 Adj, 여기서 n은 정점의 수입니다. 배열 원소 Adj[v]는 정점 v의 이웃 정점 목록입니다.
어떤 표현 방식을 선택할지는 그래프의 밀도(간선 수 대 정점 수의 비율)와 수행해야 할 연산에 따라 달라집니다. 인접 행렬은 간단하지만 희소 그래프에서는 비효율적일 수 있습니다. 인접 리스트는 희소 그래프에서 더 공간 효율적이며 정점의 이웃에 대한 접근이 더 빠릅니다.
다음은 위의 그래프를 Java에서 인접 리스트로 표현한 예시입니다:
List<Integer>[] graph = (List<Integer>[]) new List[5];
graph[0] = Arrays.asList(1, 2); // A -> B, C
graph[1] = Arrays.asList(0, 3, 4); // B -> A, D, E
graph[2] = Arrays.asList(0, 3); // C -> A, D
graph[3] = Arrays.asList(1, 2, 4); // D -> B, C, E
graph[4] = Arrays.asList(1, 3); // E -> B, D깊이 우선 탐색 (DFS)
깊이 우선 탐색(DFS)은 기본적인 그래프 탐색 알고리즘으로, 각 브랜치를 최대한 깊이 탐색한 후 다시 돌아오는 방식입니다. 연결 요소 찾기, 위상 정렬, 사이클 탐지 등 다양한 그래프 문제를 해결하는 데 사용됩니다.
DFS 알고리즘은 다음과 같이 동작합니다:
- 시작 정점 s에서 시작합니다.
- 현재 정점을 방문한 것으로 표시합니다.
- 현재 정점에 인접한 방문하지 않은 모든 정점 w를 재귀적으로 방문합니다.
- 현재 정점에 인접한 모든 정점이 방문되었다면, 현재 정점을 탐색한 정점으로 돌아갑니다.
- 아직 방문하지 않은 정점이 있다면, 하나를 선택하고 1단계부터 반복합니다.
인접 리스트를 사용한 DFS의 간단한 Java 구현은 다음과 같습니다:
boolean[] visited;
void dfs(List<Integer>[] graph, int v) {
visited[v] = true;
for (int w : graph[v]) {
if (!visited[w]) {
dfs(graph, w);
}
}
}전체 DFS 탐색을 수행하려면, visited를 모든 정점에 대해 false로 초기화한 후 각 정점 s에 대해 dfs(graph, s)를 호출하면 됩니다.
DFS는 다양한 응용 분야가 있습니다. 예를 들어, 무방향 그래프에서 연결 요소를 찾을 때 DFS를 사용할 수 있습니다.
너비 우선 탐색 (BFS)
너비 우선 탐색(BFS)은 또 다른 기본적인 그래프 탐색 알고리즘으로, 레이어 단위로 정점을 탐색합니다. 현재 깊이 수준의 모든 정점을 방문한 후 다음 깊이 수준의 정점으로 이동합니다.
BFS 알고리즘은 다음과 같이 동작합니다:
- 시작 정점 s를 방문한 것으로 표시하고 FIFO 큐에 enqueue합니다.
- 큐가 빌 때까지 다음을 반복합니다: a. 큐에서 정점 v를 dequeue합니다. b. v에 인접한 방문하지 않은 모든 정점 w를 큐에 enqueue하고 방문한 것으로 표시합니다.
- 모든 정점이 방문되면 탐색을 종료합니다.큐가 비어있지 않은 동안:
- 정점 v를 디큐합니다.
- v에 인접한 각 방문하지 않은 정점 w에 대해:
- w를 방문한 것으로 표시합니다.
- w를 큐에 인큐합니다.
여기는 인접 리스트를 사용한 BFS의 Java 구현입니다:
boolean[] visited;
void bfs(List<Integer>[] graph, int s) {
Queue<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.offer(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : graph[v]) {
if (!visited[w]) {
visited[w] = true;
queue.offer(w);
}
}
}
}BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 특히 유용합니다. 소스 정점에서 다른 정점까지의 거리는 두 정점 사이의 경로에 있는 간선의 최소 개수입니다. BFS는 최단 경로를 보장합니다.
최소 신장 트리
최소 신장 트리(MST)는 가중치가 있는 무방향 연결 그래프의 부분 그래프로, 모든 정점을 연결하고 사이클이 없으며 총 간선 가중치가 최소가 되는 트리입니다.
MST를 찾는 대표적인 두 가지 알고리즘은 Kruskal 알고리즘과 Prim 알고리즘입니다.
Kruskal 알고리즘은 다음과 같이 동작합니다:
- 각 정점을 하나의 트리로 하는 포레스트 F를 만듭니다.
- 그래프의 모든 간선을 포함하는 집합 S를 만듭니다.
- S가 비어있지 않고 F가 아직 신장 트리가 아닌 동안:
- 가중치가 가장 작은 간선을 S에서 제거합니다.
- 제거한 간선이 서로 다른 트리를 연결하는 경우, F에 추가하여 두 트리를 하나의 트리로 병합합니다.
Prim 알고리즘은 다음과 같이 동작합니다:
- 임의의 정점으로 이루어진 하나의 트리로 초기화합니다.
- 트리를 한 개의 간선씩 성장시킵니다: 트리와 트리에 속하지 않은 정점을 연결하는 간선 중 가중치가 가장 작은 간선을 트리에 추가합니다.
- 모든 정점이 트리에 포함될 때까지 2단계를 반복합니다.
여기는 Prim 알고리즘의 Java 구현입니다:
int minKey(int[] key, boolean[] mstSet, int V) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++) {
// 아직 MST에 포함되지 않은 정점 중 가장 작은 키 값을 가진 정점 찾기
if (!mstSet[v] && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}
void primMST(int[][] graph, int V) {
int[] parent = new int[V];
int[] key = new int[V];
boolean[] mstSet = new boolean[V];
// 모든 정점의 키 값을 무한대로 초기화하고, MST에 포함되지 않은 것으로 표시
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
// 시작 정점의 키 값을 0으로 설정하고, 부모를 -1로 설정
key[0] = 0;
parent[0] = -1;
// V-1개의 정점을 MST에 포함시킴
for (int count = 0; count < V - 1; count++) {
// MST에 포함되지 않은 정점 중 가장 작은 키 값을 가진 정점 선택
int u = minKey(key, mstSet, V);
mstSet[u] = true;
// 선택된 정점 u와 인접한 모든 정점 v에 대해 처리
for (int v = 0; v < V; v++) {
// 정점 u와 v 사이에 간선이 있고, v가 MST에 포함되지 않았으며, 간선 가중치가 v의 현재 키 값보다 작은 경우
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
// v의 부모를 u로 설정하고, v의 키 값을 간선 가중치로 업데이트
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// 구성된 MST 출력
printMST(parent, graph, V);
}MST(최소 신장 트리)는 통신망, 전기망, 수력망, 컴퓨터 네트워크 설계 등 다양한 분야에서 활용되며, 여행 판매원 문제와 같은 근사 해법을 제공할 수 있습니다.
최단 경로
최단 경로 문제는 그래프에서 두 정점 사이의 경로 중 가중치의 합이 최소가 되는 경로를 찾는 문제입니다. 이 문제에는 단일 출발점 최단 경로, 모든 쌍 최단 경로, 단일 도착점 최단 경로 등 다양한 변형이 있습니다.
Dijkstra 알고리즘은 가중치가 음수가 아닌 그래프에서 단일 출발점 최단 경로 문제를 해결하는 탐욕 알고리즘입니다. 이 알고리즘은 다음과 같이 동작합니다:
- 최단 경로 트리에 포함된 정점들을 추적하는
sptSet을 생성합니다. - 모든 정점에 대해 거리 값을 무한대로 초기화하고, 출발점의 거리 값을 0으로 설정합니다.
sptSet에 포함되지 않은 정점 중 가장 작은 거리 값을 가진 정점 v를 선택하여sptSet에 포함시킵니다.- 정점 v와 인접한 모든 정점 w에 대해, v를 거쳐 w로 가는 경로의 거리가 w의 현재 거리 값보다 작은 경우 w의 거리 값을 업데이트합니다.여기는 한국어 번역본입니다:
public void dijkstra(int[][] graph, int src) {
int V = graph.length;
int[] dist = new int[V];
boolean[] sptSet = new boolean[V];
// 모든 정점의 거리를 무한대로 초기화하고, 최단 경로 트리에 포함되지 않은 것으로 표시
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
// 시작 정점의 거리를 0으로 설정
dist[src] = 0;
// 모든 정점을 처리할 때까지 반복
for (int count = 0; count < V - 1; count++) {
// 아직 최단 경로 트리에 포함되지 않은 정점 중 가장 짧은 거리의 정점을 선택
int u = minDistance(dist, sptSet);
sptSet[u] = true;
// 선택된 정점 u에서 갈 수 있는 모든 정점 v에 대해 거리를 업데이트
for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
&& dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
printSolution(dist);
}벨만-포드 알고리즘은 단일 소스 정점에서 모든 다른 정점까지의 최단 경로를 찾는 또 다른 알고리즘입니다. 다이크스트라 알고리즘과 달리, 벨만-포드 알고리즘은 음수 가중치 간선을 처리할 수 있습니다.
알고리즘은 다음과 같이 작동합니다:
- 소스에서 모든 정점까지의 거리를 무한대로 초기화하고, 소스 자체의 거리를 0으로 설정합니다.
- 간선을 |V| - 1번 이완합니다. 각 간선 u-v에 대해, u에서 v로 가는 거리가 현재 v의 거리보다 짧다면 v의 거리를 업데이트합니다.
- 음수 가중치 사이클을 확인합니다. 모든 간선에 대해 이완 단계를 실행합니다. 거리가 변경되면 음수 가중치 사이클이 존재합니다.
여기는 벨만-포드 알고리즘의 Java 구현입니다:
public void bellmanFord(int[][] graph, int src) {
int V = graph.length;
int[] dist = new int[V];
// 모든 정점의 거리를 무한대로 초기화
for (int i = 0; i < V; i++)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
// |V| - 1번 간선 이완
for (int i = 1; i < V; i++) {
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
&& dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
// 음수 가중치 사이클 확인
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
&& dist[u] + graph[u][v] < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return;
}
}
}
printSolution(dist);
}
```여기는 한국어 번역본입니다. 코드 부분은 번역하지 않았고, 주석 부분만 번역했습니다.
```java
&& dist[u] + graph[u][v] < dist[v]) {
// 현재 정점 u에서 정점 v로 가는 경로의 가중치가 현재 정점 v까지의 최단 경로 가중치보다 작은 경우
dist[v] = dist[u] + graph[u][v];
// 정점 v까지의 최단 경로 가중치를 업데이트
}
}
}
}
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
&& dist[u] + graph[u][v] < dist[v]) {
// 그래프에 음수 가중치 사이클이 존재하는 경우
System.out.println("Graph contains negative weight cycle");
return;
}
}
}
printSolution(dist);
}최단 경로 알고리즘은 내비게이션 시스템, 네트워크 라우팅 프로토콜, 교통 계획 등 다양한 분야에 적용됩니다. 이는 그래프 이론의 핵심적인 알고리즘이며, 그래프 처리 작업에 필수적입니다.
결론
그래프는 다양한 문제를 모델링할 수 있는 유용하고 강력한 데이터 구조입니다. 이 장에서는 그래프의 기본 속성과 유형을 살펴보고, 깊이 우선 탐색, 너비 우선 탐색, 최소 신장 트리, 최단 경로 등의 기본적인 그래프 알고리즘을 학습했습니다.
깊이 우선 탐색과 너비 우선 탐색은 그래프를 체계적으로 탐색하는 방법이며, 많은 고급 그래프 알고리즘의 기반이 됩니다. Kruskal의 알고리즘과 Prim의 알고리즘은 최소 신장 트리를 찾는 알고리즘입니다. Dijkstra의 알고리즘과 Bellman-Ford 알고리즘은 정점 간 최단 경로를 찾는 알고리즘입니다.
이러한 핵심 개념과 알고리즘을 이해하는 것은 그래프를 효과적으로 다루고 다양한 분야의 복잡한 문제를 해결하는 데 필수적입니다. 알고리즘 학습을 계속 진행하면서 이러한 기본 기술을 바탕으로 한 더 advanced한 그래프 알고리즘을 접하게 될 것입니다.
그래프는 컴퓨터 과학 및 다른 분야의 문제를 설명하고 해결하는 강력한 도구입니다. 그래프 알고리즘을 숙달하면 다양한 문제를 모델링하고 해결할 수 있는 강력한 도구를 갖추게 될 것입니다.# 자연 언어 처리 과제
1. 문장 분류
- 문장의 주제나 감정을 분류하는 작업
- 예: 긍정적인 문장인지, 부정적인 문장인지 판단하기
2. 문장 생성
- 주어진 문맥에 맞는 새로운 문장을 생성하는 작업
- 예: 주어진 문장을 바탕으로 더 자연스러운 문장 만들기
3. 기계 번역
- 한 언어로 된 문장을 다른 언어로 번역하는 작업
- 예: 영어 문장을 한국어로 번역하기
4. 질문 답변
- 주어진 질문에 대한 답변을 생성하는 작업
- 예: 사용자의 질문에 대해 적절한 답변 제공하기
# 문장 분류 예제
import numpy as np
from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
# 20개 뉴스 그룹 데이터셋 불러오기
newsgroups = fetch_20newsgroups(subset='all')
X_train = newsgroups.data
y_train = newsgroups.target
# 단어 빈도수 기반 특징 추출
vectorizer = CountVectorizer()
X_train_vectorized = vectorizer.fit_transform(X_train)
# 나이브 베이즈 분류기 학습 및 평가
clf = MultinomialNB()
clf.fit(X_train_vectorized, y_train)
score = clf.score(X_train_vectorized, y_train)
print(f'Accuracy: {score:.2f}')자연 언어 처리 과제
1. 문장 분류
- 문장의 주제나 감정을 분류하는 작업
- 예: 긍정적인 문장인지, 부정적인 문장인지 판단하기
2. 문장 생성
- 주어진 문맥에 맞는 새로운 문장을 생성하는 작업
- 예: 주어진 문장을 바탕으로 더 자연스러운 문장 만들기
3. 기계 번역
- 한 언어로 된 문장을 다른 언어로 번역하는 작업
- 예: 영어 문장을 한국어로 번역하기
4. 질문 답변
- 주어진 질문에 대한 답변을 생성하는 작업
- 예: 사용자의 질문에 대해 적절한 답변 제공하기
# 문장 분류 예제
import numpy as np
from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
# 20개 뉴스 그룹 데이터셋 불러오기
newsgroups = fetch_20newsgroups(subset='all')
X_train = newsgroups.data
y_train = newsgroups.target
# 단어 빈도수 기반 특징 추출
vectorizer = CountVectorizer()
X_train_vectorized = vectorizer.fit_transform(X_train)
# 나이브 베이즈 분류기 학습 및 평가
clf = MultinomialNB()
clf.fit(X_train_vectorized, y_train)
score = clf.score(X_train_vectorized, y_train)
print(f'Accuracy: {score:.2f}')