최소 스패닝 트리 (MST, Minimum Spanning Tree) : 프림 (Prim)

스패닝 트리 (Spanning Tree) ?

• 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다.
• 아래와 같은 예시들이 스패닝 트리라고 할 수 있다.

• 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다.
• 또한, 트리 형태여야 한다는 말은 선택된 간선이 사이클을 이루지 않는다는 의미여, 정점들이 부모-자식 관계로 연결될 필요는 없다는 것이다.

 

최소 스패닝 트리 (MST, Minimum Spanning Tree) ?

• 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리이다.
• 최소 스패닝 트리를 구할 수 있는 알고리즘은 두 가지가 있다.
  • 크루스칼 (Kruskal) 알고리즘 : Kruskal Algorithm
  • 프림 (Prim) 알고리즘

 

프림 (Prim) 알고리즘

• 크루스칼과 달리 프림은 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하며 스패닝 트리가 될 때까지 키워 간다.
• 따라서 항상 선택된 간선들은 중간 과정에서도 항상 연결된 트리를 이루게 된다.
• 이미 만들어진 트리에 인접한 간선만을 고려한다는 점을 제외하면 크루스칼과 동일하다.
• 우선순위 큐를 사용하면 시간 복잡도 O(E * log V) 를 갖는다.
• 프림 알고리즘은 노드의 수에 영향을 받기 때문에, 노드의 수가 적고 간선의 수가 많은 그래프에서 효율적이다.

과정

• 스패닝 트리에 포함된 정점은 파란색 원으로, 포함된 간선은 빨간색 굵은 실선으로 나타냈다.
• 이때 그림에서 회색 점선으로 표시된 간선들은 다음 단계에 트리에 추가될 가능성이 있는 후보 간선들로, 트리에 속한 정점 하나와 트리에 속하지 않은 정점 하나를 연결한다.
• Roop 3에서 간선 (B, D) 는 이미 트리에 속한 정점들을 연결하기 때문에 후보 간선이 아니다.

 

Code

그래프를 형성하는 Graph 클래스

class Graph {
    List<Edge>[] edge;
 
    public Graph(int V) {
        edge = new LinkedList[V + 1];
 
        for (int i = 1; i <= V; i++)
            edge[i] = new LinkedList<>();
    }
 
    // 양방향 그래프
    public void AddEdge(int x, int y, int cost) {
        edge[x].add(new Edge(x, y, cost));
        edge[y].add(new Edge(y, x, cost));
    }
}

 

간선의 정보를 담는 Edge 클래스

class Edge implements Comparable<Edge> {
    int x, y, cost;
 
    public Edge(int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
 
    @Override // 우선순위 큐를 사용하기 위한 함수 오버라이딩
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}

 

Prim 알고리즘을 수행하는 함수

public static void Prim() {
    PriorityQueue<Edge> pq = new PriorityQueue<>(); // 가중치가 낮은 순대로 간선을 정렬할 우선순위
    Queue<Integer> queue = new LinkedList<>();      // 정점방문 스케줄 처리를 위한 큐
 
    queue.add(1);                                   // 정점 1을 시작정점으로 선택
 
    while (!queue.isEmpty()) {
        int from = queue.poll();
        visited[from] = true;
 
        for (Edge edge : graph.edge[from]) {        // 현재 정점 from과 연결된 간선 중
            if (!visited[edge.to]) {                // 아직 정점 to를 방문하지 않았다면
                pq.add(edge);                       // 우선순위 큐에 간선을 추가한다.
            }
        }
 
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();                  // 우선순위 큐에 의해 가중치가 가장 작은 간선이 나올 것이며,
            if (!visited[edge.to]) {                // 간선이 연결된 정점 to를 방문한 적이 없다면,
                queue.add(edge.to);                 // 큐에 삽입하여 다음에 방문한다.
                visited[edge.to] = true;            // 방문했던 정점을 다시 방문하지 않도록 방문표시.
                mst.add(edge);                      // 최소 스패닝 트리를 구성하는 간선 추가.
                min += edge.cost;                   // 총 최소 가중치 합을 구하기 위해 덧셈.
                break;
            }
        }
    }
}

 

전체 코드

import java.util.*;
 
public class test1 {
    static int V, E, min = 0;
    static Graph graph;
    static boolean[] visited;
    static ArrayList<Edge> mst;
 
    public static void main(String[] args) {
        V = 9;
        E = 14;
        visited = new boolean[V + 1];
        mst = new ArrayList<>();
        graph = new Graph(V);
 
        graph.AddEdge(1, 2, 4);
        graph.AddEdge(2, 3, 8);
        graph.AddEdge(3, 4, 7);
        graph.AddEdge(4, 5, 9);
        graph.AddEdge(5, 6, 10);
        graph.AddEdge(6, 7, 2);
        graph.AddEdge(7, 8, 1);
        graph.AddEdge(8, 9, 7);
        graph.AddEdge(1, 8, 8);
        graph.AddEdge(2, 8, 11);
        graph.AddEdge(3, 6, 4);
        graph.AddEdge(3, 9, 2);
        graph.AddEdge(4, 6, 14);
        graph.AddEdge(7, 9, 6);
 
        Prim();
 
        for (Edge edge : mst)
            System.out.println(edge.from + " - " + edge.to + " cost : " + edge.cost);
 
        System.out.println(min);
    }
 
    public static void Prim() {
        PriorityQueue<Edge> pq = new PriorityQueue<>(); // 가중치가 낮은 순대로 간선을 정렬할 우선순위
        Queue<Integer> queue = new LinkedList<>();      // 정점방문 스케줄 처리를 위한 큐
 
        queue.add(1);                                   // 정점 1을 시작정점으로 선택
 
        while (!queue.isEmpty()) {
            int from = queue.poll();
            visited[from] = true;
 
            for (Edge edge : graph.edge[from]) {        // 현재 정점 from과 연결된 간선 중
                if (!visited[edge.to]) {                // 아직 정점 to를 방문하지 않았다면
                    pq.add(edge);                       // 우선순위 큐에 간선을 추가한다.
                }
            }
 
            while (!pq.isEmpty()) {
                Edge edge = pq.poll();                  // 가중치가 가장 적은 간선이 나올 것이며,
                if (!visited[edge.to]) {                // 간선이 연결된 정점 to를 방문한 적이 없다면,
                    queue.add(edge.to);                 // 큐에 삽입하여 다음에 방문한다.
                    visited[edge.to] = true;            // 방문했던 정점을 다시 방문하지 않도록 방문표시.
                    mst.add(edge);                      // 최소 스패닝 트리를 구성하는 간선 추가.
                    min += edge.cost;                   // 총 최소 가중치 합을 구하기 위해 덧셈.
                    break;
                }
            }
        }
    }
}
 
class Graph {
    List<Edge>[] edge;
 
    public Graph(int V) {
        edge = new LinkedList[V + 1];
 
        for (int i = 1; i <= V; i++)
            edge[i] = new LinkedList<>();
    }
 
    // 양방향 그래프
    public void AddEdge(int from, int to, int cost) {
        edge[from].add(new Edge(from, to, cost));
        edge[to].add(new Edge(to, from, cost));
    }
}
 
class Edge implements Comparable<Edge> {
    int from, to, cost;
 
    public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
 
    @Override // 우선순위 큐를 사용하기 위한 함수 오버라이딩
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}