다익스트라 알고리즘
가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘. 음의 가중치가 없을 때 사용 가능하다.
자바 코드 예시:
import java.util.*;
public class Graph {
private int numVertices;
private LinkedList<Edge>[] adjList;
private class Edge {
int vertex;
int weight;
Edge(int v, int w) {
vertex = v;
weight = w;
}
}
public Graph(int vertices) {
numVertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEdge(int src, int dest, int weight) {
adjList[src].add(new Edge(dest, weight));
}
public void dijkstra(int startVertex) {
int[] distances = new int[numVertices];
boolean[] visited = new boolean[numVertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[startVertex] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
pq.add(new Edge(startVertex, 0));
while (!pq.isEmpty()) {
Edge current = pq.poll();
if (visited[current.vertex]) continue;
visited[current.vertex] = true;
for (Edge e : adjList[current.vertex]) {
if (!visited[e.vertex] && distances[current.vertex] + e.weight < distances[e.vertex]) {
distances[e.vertex] = distances[current.vertex] + e.weight;
pq.add(new Edge(e.vertex, distances[e.vertex]));
}
}
}
for (int i = 0; i < numVertices; i++) {
System.out.println("Distance from " + startVertex + " to " + i + " is " + distances[i]);
}
}
public static void main(String[] args) {
Graph g = new Graph(5);
g.addEdge(0, 1, 9);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(0, 4, 3);
g.addEdge(2, 1, 2);
g.addEdge(2, 3, 4);
g.dijkstra(0);
}
}
출처 : https://velog.io/@agugu95/Prims-Algorithm%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
크루스칼 알고리즘
최소 신장 트리를 찾는 알고리즘. 가중치가 있는 그래프에서 가장 가벼운 가중치부터 선택하여, 사이클을 형성하지 않는 선에서 최소 비용으로 모든 노드를 연결한다.
자바 코드 예시:
import java.util.*;
public class Graph {
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
class Subset {
int parent, rank;
}
int vertices, edges;
Edge[] edge;
Graph(int v, int e) {
vertices = v;
edges = e;
edge = new Edge[edges];
for (int i = 0; i < e; ++i) {
edge[i] = new Edge();
}
}
int find(Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
void union(Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
void KruskalMST() {
Edge result[] = new Edge[vertices];
int e = 0;
int i = 0;
for (i = 0; i < vertices; ++i) {
result[i] = new Edge();
}
Arrays.sort(edge);
Subset subsets[] = new Subset[vertices];
for (i = 0; i < vertices; ++i) {
subsets[i] = new Subset();
subsets[i].parent = i;
subsets[i].rank = 0;
}
i = 0;
while (e < vertices - 1) {
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
union(subsets, x, y);
}
}
for (i = 0; i < e; ++i) {
System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
}
}
public static void main(String[] args) {
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 10;
// add edge 0-2
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
// add edge 0-3
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
// add edge 1-3
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
// add edge 2-3
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 4;
graph.KruskalMST();
}
}프림 알고리즘 (Prim's Algorithm)
가중치가 있는 연결 그래프에서 최소 신장 트리를 찾는 알고리즘이야. 프림 알고리즘은 임의의 정점에서 시작하여, 선택된 정점들에 인접한 정점들 중 최소 가중치 간선으로 연결된 정점을 선택하며 신장 트리를 확장해 나간다.
import java.util.*;
import java.util.PriorityQueue;
public class Graph {
private List<List<Edge>> adjList;
public Graph(int vertices) {
adjList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int src, int dest, int weight) {
adjList.get(src).add(new Edge(src, dest, weight));
adjList.get(dest).add(new Edge(dest, src, weight));
}
public void primMST() {
boolean[] inMST = new boolean[adjList.size()];
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
int start = 0; // Starting from vertex 0
// Add all edges from vertex 0
for (Edge e : adjList.get(start)) {
pq.add(e);
}
inMST[start] = true;
while (!pq.isEmpty()) {
Edge e = pq.poll();
if (inMST[e.dest]) continue;
// Include this edge in MST
System.out.println(e.src + " - " + e.dest + " : " + e.weight);
inMST[e.dest] = true;
for (Edge next : adjList.get(e.dest)) {
if (!inMST[next.dest]) {
pq.add(next);
}
}
}
}
class Edge {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
public static void main(String[] args) {
Graph g = new Graph(4);
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 6);
g.addEdge(0, 3, 5);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.primMST();
}
}
유니온-파인드 알고리즘
유니온-파인드 알고리즘은 서로소 집합 자료구조로, 집합의 합치기(union)와 찾기(find) 연산을 지원해. 크루스칼 알고리즘에서는 간선을 선택할 때 사이클이 형성되는지를 유니온-파인드로 확인하여 사이클을 방지할 수 있다.
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// Find the root of the node, with path compression
public int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // Path compression
}
return parent[node];
}
// Union by rank
public void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 != root2) {
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else {
parent[root2] = root1;
rank[root1]++;
}
}
}
public static void main(String[] args) {
// Example usage
UnionFind uf = new UnionFind(10); // Create a union-find for 10 elements
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
uf.union(6, 7);
System.out.println("Find(1): " + uf.find(1));
System.out.println("Find(2): " + uf.find(2));
System.out.println("Find(3): " + uf.find(3));
System.out.println("Find(4): " + uf.find(4));
System.out.println("Find(5): " + uf.find(5));
System.out.println("Find(6): " + uf.find(6));
System.out.println("Find(7): " + uf.find(7));
System.out.println("Find(8): " + uf.find(8));
// Check if two elements are in the same set
System.out.println("1 and 3 are connected: " + (uf.find(1) == uf.find(3)));
System.out.println("4 and 6 are connected: " + (uf.find(4) == uf.find(6)));
}
}
프림 알고리즘은 우선순위 큐를 활용하여 각 단계에서 최소 가중치를 갖는 간선을 선택하고, 크루스칼 알고리즘은 유니온-파인드를 사용하여 간선 선택 시 사이클을 방지해 최소 신장 트리를 구성한다.
이 두 알고리즘은 그래프에서 최소 신장 트리를 찾는 데 자주 사용된다!.
끝!
강준규