8. 그래프 알고리즘
8.1 최소 신장 트리(MST)
최소 신장 트리(Minimum Spanning Tree, MST)
최소 신장 트리 알고리즘은 주어진 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제입니다. 대표적인 MST 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다.
MST 알고리즘은 네트워크 설계, 회로 설계, 도로망 설계 등에서 널리 사용됩니다. MST의 시간 복잡도는 알고리즘에 따라 다르지만, 크루스칼 알고리즘은 일반적으로 \(O(E \log E)\)이고, 프림 알고리즘은 \(O(E \log V)\)입니다.
역사적 배경
MST 문제는 1926년 Otakar Borůvka에 의해 전기 네트워크 설계 문제를 해결하기 위해 처음 소개되었습니다. 이후 1956년에 Joseph Kruskal과 Robert Prim이 각각 독립적으로 MST 알고리즘을 개발하였습니다.
// 크루스칼 알고리즘 예시
import java.util.*;
class Edge implements Comparable {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight; // 가중치를 기준으로 정렬
}
}
class Graph {
int V, E;
Edge[] edges;
public Graph(int V, int E) {
this.V = V;
this.E = E;
edges = new Edge[E];
}
public void addEdge(int i, int src, int dest, int weight) {
edges[i] = new Edge(src, dest, weight);
}
public int find(int[] parent, int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
public void union(int[] parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
public void kruskalMST() {
Arrays.sort(edges); // 모든 간선을 가중치 기준으로 정렬
int[] parent = new int[V];
Arrays.fill(parent, -1);
ArrayList result = new ArrayList<>();
for (Edge edge : edges) {
int x = find(parent, edge.src);
int y = find(parent, edge.dest);
if (x != y) {
result.add(edge);
union(parent, x, y);
}
}
System.out.println("Edges in the constructed MST:");
for (Edge edge : result) {
System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
}
}
}
public class KruskalAlgorithm {
public static void main(String[] args) {
int V = 4; // 그래프의 정점 수
int E = 5; // 그래프의 간선 수
Graph graph = new Graph(V, E);
graph.addEdge(0, 0, 1, 10);
graph.addEdge(1, 0, 2, 6);
graph.addEdge(2, 0, 3, 5);
graph.addEdge(3, 1, 3, 15);
graph.addEdge(4, 2, 3, 4);
graph.kruskalMST(); // 크루스칼 알고리즘 실행
}
}
8.2 최단 경로 알고리즘
최단 경로 알고리즘(Shortest Path Algorithm)
최단 경로 알고리즘은 주어진 그래프에서 두 정점 사이의 최단 경로를 찾는 문제입니다. 대표적인 최단 경로 알고리즘으로는 다익스트라(Dijkstra) 알고리즘과 벨만-포드(Bellman-Ford) 알고리즘이 있습니다.
최단 경로 알고리즘은 네비게이션 시스템, 네트워크 라우팅, 물류 경로 최적화 등에서 사용됩니다. 다익스트라 알고리즘은 시간 복잡도가 \(O(V^2)\) 또는 \(O(E + V \log V)\)이며, 벨만-포드 알고리즘은 \(O(VE)\)입니다.
역사적 배경
최단 경로 문제는 1956년 Edsger Dijkstra에 의해 처음 소개되었습니다. 다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 효율적으로 찾는 방법을 제공하며, 이후 다양한 변형과 최적화가 개발되었습니다.
// 다익스트라 알고리즘 예시
import java.util.*;
class Graph {
private int V;
private LinkedList adj[];
class Node implements Comparable {
int vertex, weight;
public Node(int v, int w) {
vertex = v;
weight = w;
}
@Override
public int compareTo(Node node) {
return this.weight - node.weight; // 가중치를 기준으로 정렬
}
}
Graph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<>();
}
}
void addEdge(int u, int v, int w) {
adj[u].add(new Node(v, w));
adj[v].add(new Node(u, w)); // 무방향 그래프
}
void dijkstra(int src) {
PriorityQueue pq = new PriorityQueue<>();
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
pq.add(new Node(src, 0));
dist[src] = 0;
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.vertex;
for (Node neighbor : adj[u]) {
int v = neighbor.vertex;
int weight = neighbor.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new Node(v, dist[v]));
}
}
}
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++) {
System.out.println(i + " \t\t " + dist[i]);
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1, 9);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(0, 4, 3);
graph.addEdge(2, 1, 2);
graph.addEdge(2, 3, 4);
graph.dijkstra(0); // 다익스트라 알고리즘 실행
}
}
8.3 사이클 찾기 알고리즘
사이클 찾기 알고리즘(Cycle Detection Algorithm)
사이클 찾기 알고리즘은 그래프 내에 사이클(순환 구조)이 존재하는지 여부를 탐색하는 문제입니다. 대표적인 사이클 찾기 알고리즘으로는 DFS 기반 탐색과 유니온-파인드(Union-Find) 알고리즘이 있습니다.
사이클 찾기 알고리즘은 네트워크 분석, 회로 설계, 데이터베이스의 무결성 검사 등에서 사용됩니다. DFS 기반 탐색은 시간 복잡도가 \(O(V + E)\)이며, 유니온-파인드 알고리즘은 \(O(E \log V)\)입니다.
역사적 배경
사이클 찾기 문제는 그래프 이론의 기본적인 문제 중 하나로, 19세기 수학자들이 처음 연구하기 시작했습니다. 유니온-파인드 알고리즘은 1960년에 John Hopcroft와 Robert Tarjan에 의해 소개되었습니다.
// 유니온-파인드 알고리즘을 사용한 사이클 찾기 예시
class Graph {
int V, E;
Edge[] edges;
class Edge {
int src, dest;
}
Graph(int v, int e) {
V = v;
E = e;
edges = new Edge[E];
for (int i = 0; i < e; ++i) {
edges[i] = new Edge();
}
}
int find(int[] parent, int i) {
if (parent[i] == -1
return i;
return find(parent, parent[i]);
}
void union(int[] parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
boolean isCycle(Graph graph) {
int[] parent = new int[graph.V];
Arrays.fill(parent, -1);
for (int i = 0; i < graph.E; ++i) {
int x = find(parent, graph.edges[i].src);
int y = find(parent, graph.edges[i].dest);
if (x == y)
return true;
union(parent, x, y);
}
return false;
}
public static void main(String[] args) {
Graph graph = new Graph(3, 3);
graph.edges[0].src = 0;
graph.edges[0].dest = 1;
graph.edges[1].src = 1;
graph.edges[1].dest = 2;
graph.edges[2].src = 0;
graph.edges[2].dest = 2;
if (graph.isCycle(graph))
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't contain cycle");
}
}
이 코드에서 우리는 유니온-파인드 알고리즘을 사용하여 그래프 내에서 사이클을 찾습니다. 각 간선을 검사하며, 두 정점이 같은 집합에 속해 있는지 확인하여 사이클 여부를 판단합니다.
8.4 네트워크 플로우 알고리즘
네트워크 플로우 알고리즘(Network Flow Algorithm)
네트워크 플로우 알고리즘은 그래프에서 최대 유량(최대 흐름)을 찾는 문제입니다. 대표적인 네트워크 플로우 알고리즘으로는 포드-풀커슨(Ford-Fulkerson) 알고리즘과 에드몬드-카프(Edmonds-Karp) 알고리즘이 있습니다.
네트워크 플로우 알고리즘은 물류 및 교통 네트워크 최적화, 통신 네트워크 설계, 이미지 분할 등에서 사용됩니다. 에드몬드-카프 알고리즘의 시간 복잡도는 \(O(VE^2)\)입니다.
역사적 배경
네트워크 플로우 문제는 1954년에 L. R. Ford Jr.와 D. R. Fulkerson에 의해 처음 소개되었습니다. 이후 1972년에 Jack Edmonds와 Richard Karp가 개선된 알고리즘을 개발하였습니다.
// 에드몬드-카프 알고리즘 예시
import java.util.LinkedList;
class Graph {
private int V;
private int[][] capacity;
private int[][] flow;
public Graph(int V) {
this.V = V;
capacity = new int[V][V];
flow = new int[V][V];
}
public void addEdge(int u, int v, int cap) {
capacity[u][v] = cap;
}
private boolean bfs(int source, int sink, int[] parent) {
boolean[] visited = new boolean[V];
LinkedList queue = new LinkedList<>();
queue.add(source);
visited[source] = true;
parent[source] = -1;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < V; v++) {
if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
queue.add(v);
parent[v] = u;
visited[v] = true;
}
}
}
return visited[sink];
}
public int edmondsKarp(int source, int sink) {
int maxFlow = 0;
int[] parent = new int[V];
while (bfs(source, sink, parent)) {
int pathFlow = Integer.MAX_VALUE;
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
pathFlow = Math.min(pathFlow, capacity[u][v] - flow[u][v]);
}
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
flow[u][v] += pathFlow;
flow[v][u] -= pathFlow;
}
maxFlow += pathFlow;
}
return maxFlow;
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1, 16);
graph.addEdge(0, 2, 13);
graph.addEdge(1, 2, 10);
graph.addEdge(1, 3, 12);
graph.addEdge(2, 1, 4);
graph.addEdge(2, 4, 14);
graph.addEdge(3, 2, 9);
graph.addEdge(3, 5, 20);
graph.addEdge(4, 3, 7);
graph.addEdge(4, 5, 4);
System.out.println("The maximum possible flow is " + graph.edmondsKarp(0, 5));
}
}
이 코드에서 우리는 에드몬드-카프 알고리즘을 사용하여 네트워크 플로우 문제를 해결합니다. BFS를 사용하여 증가 경로를 찾고, 각 경로의 최소 용량만큼 플로우를 증가시켜 최대 유량을 계산합니다.