Java를 사용하여 최소 신장 트리 알고리즘을 구현하는 방법

Java를 사용하여 최소 신장 트리 알고리즘을 구현하는 방법

최소 신장 트리 알고리즘은 그래프 이론의 고전적인 문제로, 가중치 연결 그래프의 최소 신장 트리를 해결하는 데 사용됩니다. 이 기사에서는 Java 언어를 사용하여 이 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

1. 문제 설명
   각 간선에 가중치가 있는 연결된 그래프 G가 주어지면 T의 모든 간선 가중치의 합이 최소가 되는 최소 스패닝 트리 T를 찾아야 합니다.
2. Prim의 알고리즘
   Prim의 알고리즘은 최소 신장 트리 문제를 해결하는 데 사용되는 그리디 알고리즘입니다. 기본 아이디어는 정점에서 시작하여 스패닝 트리를 점진적으로 확장하여 모든 정점이 스패닝 트리에 추가될 때까지 매번 기존 스패닝 트리에 가장 가까운 정점을 선택하는 것입니다.

다음은 Prim 알고리즘의 Java 구현 예입니다.

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Prim {
    public static List<Edge> calculateMST(List<List<Edge>> graph) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        Queue<Edge> pq = new PriorityQueue<>();
        
        // Start from vertex 0
        int start = 0;
        visited[start] = true;
        for (Edge e : graph.get(start)) {
            pq.offer(e);
        }
        
        List<Edge> mst = new ArrayList<>();
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int from = e.from;
            int to = e.to;
            int weight = e.weight;
            
            if (visited[to]) {
                continue;
            }
            
            visited[to] = true;
            mst.add(e);
            
            for (Edge next : graph.get(to)) {
                if (!visited[next.to]) {
                    pq.offer(next);
                }
            }
        }
        
        return mst;
    }
}

3. Kruskal 알고리즘
   Kruskal 알고리즘도 최소 스패닝 트리 문제를 해결하는 데 사용되는 그리디 알고리즘입니다. 기본 아이디어는 가중치에 따라 그래프의 모든 가장자리를 작은 것부터 큰 것까지 정렬한 다음 가장자리를 추가할 때 가장자리의 두 끝점이 동일하지 않은 경우 차례로 스패닝 트리에 추가하는 것입니다. 연결된 구성 요소인 경우 이러한 가장자리를 스패닝 트리에 추가할 수 있습니다. 두 끝점은 연결된 구성 요소로 병합됩니다.

다음은 Kruskal 알고리즘의 Java 구현 예입니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Kruskal {
    public static List<Edge> calculateMST(List<Edge> edges, int n) {
        List<Edge> mst = new ArrayList<>();
        Collections.sort(edges);
        
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        for (Edge e : edges) {
            int from = e.from;
            int to = e.to;
            int weight = e.weight;
            
            int parentFrom = findParent(from, parent);
            int parentTo = findParent(to, parent);
            
            if (parentFrom != parentTo) {
                mst.add(e);
                parent[parentFrom] = parentTo;
            }
        }
        
        return mst;
    }
    
    private static int findParent(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = findParent(parent[x], parent);
        }
        
        return parent[x];
    }
}

4. 사용 예
   다음은 간단한 사용 예입니다.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<List<Edge>> graph = new ArrayList<>();
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        
        graph.get(0).add(new Edge(0, 1, 2));
        graph.get(0).add(new Edge(0, 2, 3));
        graph.get(1).add(new Edge(1, 0, 2));
        graph.get(1).add(new Edge(1, 2, 1));
        graph.get(1).add(new Edge(1, 3, 5));
        graph.get(2).add(new Edge(2, 0, 3));
        graph.get(2).add(new Edge(2, 1, 1));
        graph.get(2).add(new Edge(2, 3, 4));
        graph.get(3).add(new Edge(3, 1, 5));
        graph.get(3).add(new Edge(3, 2, 4));
        
        List<Edge> mst = Prim.calculateMST(graph);
        System.out.println("Prim算法得到的最小生成树：");
        for (Edge e : mst) {
            System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
        }
        
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 2, 3));
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(1, 3, 5));
        edges.add(new Edge(2, 3, 4));
        
        mst = Kruskal.calculateMST(edges, 4);
        System.out.println("Kruskal算法得到的最小生成树：");
        for (Edge e : mst) {
            System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
        }
    }
}

위의 예제 프로그램을 실행하면 다음과 같은 출력을 얻을 수 있습니다.

Prim算法得到的最小生成树：
0 -> 1，权重：2
1 -> 2，权重：1
2 -> 3，权重：4
Kruskal算法得到的最小生成树：
1 -> 2，权重：1
0 -> 1，权重：2
2 -> 3，权重：4

위는 Java에서 최소 스패닝 트리 알고리즘을 구현하기 위한 구체적인 코드 예제입니다. 이러한 샘플 코드를 통해 독자는 최소 신장 트리 알고리즘의 구현 과정과 원리를 더 잘 이해하고 배울 수 있습니다. 이 글이 독자들에게 도움이 되기를 바랍니다.

위 내용은 Java를 사용하여 최소 신장 트리 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!