[java] 프림 알고리즘

04 Dec 2023

java

프림 알고리즘의 구현은 다음과 같습니다.

임의의 정점을 선택하여 시작 정점으로 지정합니다.
시작 정점과 연결된 간선 중 최소 비용 간선을 선택합니다.
선택한 간선의 도착 정점을 방문한 것으로 표시합니다.
선택한 간선의 도착 정점과 연결된 간선 중 최소 비용 간선을 선택합니다.
모든 정점이 방문될 때까지 3, 4 단계를 반복합니다.

프림 알고리즘은 우선순위 큐를 사용하여 구현할 수 있습니다. 아래는 Java로 프림 알고리즘을 구현한 예시 코드입니다.

import java.util.*;

class Edge implements Comparable<Edge> {
    int source;
    int destination;
    int weight;

    public Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class PrimAlgorithm {
    public static void primMST(List<List<Edge>> graph, int startVertex) {
        int numVertices = graph.size();
        boolean[] visited = new boolean[numVertices];
        PriorityQueue<Edge> minHeap = new PriorityQueue<>();

        visited[startVertex] = true;
        for (Edge edge : graph.get(startVertex)) {
            minHeap.add(edge);
        }

        while (!minHeap.isEmpty()) {
            Edge edge = minHeap.remove();
            if (!visited[edge.destination]) {
                visited[edge.destination] = true;
                System.out.println("Edge: " + edge.source + " - " + edge.destination + ", Weight: " + edge.weight);

                for (Edge neighbor : graph.get(edge.destination)) {
                    if (!visited[neighbor.destination]) {
                        minHeap.add(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int numVertices = 5;
        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i < numVertices; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프에 간선 추가
        graph.get(0).add(new Edge(0, 1, 2));
        graph.get(0).add(new Edge(0, 3, 6));
        graph.get(1).add(new Edge(1, 2, 3));
        graph.get(1).add(new Edge(1, 3, 8));
        graph.get(1).add(new Edge(1, 4, 5));
        graph.get(2).add(new Edge(2, 4, 7));
        graph.get(3).add(new Edge(3, 4, 9));

        primMST(graph, 0);
    }
}

위의 코드는 5개의 정점과 7개의 간선으로 이루어진 그래프에서 프림 알고리즘을 실행하는 예시입니다. 시작 정점을 0으로 설정하고, 최소 비용 신장 트리의 간선을 출력합니다.

프림 알고리즘은 시간 복잡도가 O(E log V)입니다. E는 간선의 수, V는 정점의 수를 의미합니다. 이 알고리즘을 사용하면 그래프에서 최소 비용 신장 트리를 효율적으로 구할 수 있습니다.

참고 자료: