7. 알고리즘 신장 트리

알고리즘에서 신장 트리(Spanning Tree)는 그래프의 모든 정점을 포함하면서 사이클이 없는 트리입니다. 신장 트리는 주어진 그래프의 일부 간선을 선택하여 만들어지며, 원래 그래프의 모든 정점을 연결하는 최소한의 간선을 포함합니다. 신장 트리는 그래프에서 필요한 연결성과 최소한의 비용을 유지하기 위해 사용됩니다.

신장 트리를 구하는 알고리즘 중 대표적인 것은 "최소 신장 트리(Minimum Spanning Tree)" 알고리즘입니다. 대표적인 최소 신장 트리 알고리즘으로는 "크루스칼(Kruskal)" 알고리즘과 "프림(Prim)" 알고리즘이 있습니다.

1. 크루스칼(Kruskal) 알고리즘

크루스칼(Kruskal) 알고리즘은 주어진 그래프에서 사이클을 형성하지 않으면서 가장 작은 가중치의 간선을 선택하여 최소 신장 트리를 구성하는 방법입니다.

크루스칼 알고리즘의 동작 과정은 다음과 같습니다

1. 모든 간선을 가중치 순으로 정렬합니다.

2. 가장 작은 가중치를 가진 간선부터 선택합니다.

3. 선택한 간선이 사이클을 형성하지 않는 경우에만 해당 간선을 최소 신장 트리에 추가합니다.

4. 모든 간선을 검사할 때까지 위의 과정을 반복합니다.

예시

아래는 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구하는 예시 코드입니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Edge {
    int source;
    int destination;
    int weight;

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

class KruskalMST {
    int vertices;
    List<Edge> edges;

    public KruskalMST(int vertices) {
        this.vertices = vertices;
        edges = new ArrayList<>();
    }

    public void addEdge(int source, int destination, int weight) {
        Edge edge = new Edge(source, destination, weight);
        edges.add(edge);
    }

    public void findMinimumSpanningTree() {
        edges.sort(Comparator.comparingInt(e -> e.weight));

        int[] parent = new int[vertices];
        Arrays.fill(parent, -1);

        List<Edge> minimumSpanningTree = new ArrayList<>();

        for (Edge edge : edges) {
            int sourceParent = find(parent, edge.source);
            int destinationParent = find(parent, edge.destination);

            if (sourceParent != destinationParent) {
                minimumSpanningTree.add(edge);
                union(parent, sourceParent, destinationParent);
            }
        }

        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : minimumSpanningTree) {
            System.out.println(edge.source + " - " + edge.destination + " : " + edge.weight);
        }
    }

    private int find(int[] parent, int vertex) {
        if (parent[vertex] == -1) {
            return vertex;
        }
        return find(parent, parent[vertex]);
    }

    private void union(int[] parent, int x, int y) {
        int xSet = find(parent, x);
        int ySet = find(parent, y);
        parent[xSet] = ySet;
    }
}

public class Main {
    public static void main(String[] args) {
        int vertices = 6;
        KruskalMST mst = new KruskalMST(vertices);

        mst.addEdge(0, 1, 6);
        mst.addEdge(0, 2, 1);
        mst.addEdge(0, 3, 5);
        mst.addEdge(1, 2, 5);
        mst.addEdge(1, 4, 3);
        mst.addEdge(2, 4, 6);
        mst.addEdge(2, 3, 5);
        mst.addEdge(2, 5, 4);
        mst.addEdge(3, 5, 2);
        mst.addEdge(4, 5, 6);

        mst.findMinimumSpanningTree();
    }
}

위의 코드는 Kruskal 알고리즘을 사용하여 주어진 그래프의 최소 신장 트리를 구하는 예시입니다. 코드를 간단히 설명하면 다음과 같습니다.

• Edge 클래스는 간선을 나타내는 클래스로, 시작 정점(source), 도착 정점(destination), 가중치(weight)를 가지고 있습니다.

• KruskalMST 클래스는 Kruskal 알고리즘을 구현한 클래스로, 정점의 개수(vertices)와 간선들의 리스트(edges)를 가지고 있습니다.

• addEdge 메서드를 사용하여 간선을 추가할 수 있습니다.

• findMinimumSpanningTree 메서드는 Kruskal 알고리즘을 실행하여 최소 신장 트리를 찾습니다.

  • edges 리스트를 가중치를 기준으로 오름차순으로 정렬합니다.

  • parent 배열을 사용하여 각 정점의 부모 정점을 저장합니다. 초기에는 -1로 초기화합니다.

  • minimumSpanningTree 리스트에 최소 신장 트리의 간선들을 저장합니다.

  • 간선들을 순회하면서 사이클이 생성되지 않는 경우에만 간선을 선택하고, 부모 정점을 갱신합니다.

• 마지막으로 main 메서드에서 예시 그래프를 생성하고 findMinimumSpanningTree 메서드를 호출하여 최소 신장 트리를 출력합니다.

실행 결과는 다음과 같습니다.

Minimum Spanning Tree:
0 - 2 : 1
3 - 5 : 2
1 - 4 : 3
2 - 5 : 4
1 - 2 : 5

위의 예시 그래프에서 생성된 최소 신장 트리의 간선들이 출력되었습니다. 각 간선은 시작 정점, 도착 정점, 가중치로 표시되며, 모든 정점을 포함하면서 사이클이 없는 최소 신장 트리가 생성되었습니다.

2. 프림(Prim) 알고리즘

프림(Prim) 알고리즘은 주어진 그래프에서 정점을 하나씩 추가하면서 최소 비용의 간선을 선택하여 최소 신장 트리를 구성하는 방법입니다.

프림 알고리즘의 동작 과정은 다음과 같습니다

1. 임의의 시작 정점을 선택합니다.

2. 선택한 정점과 연결된 간선 중에서 가장 작은 가중치를 가진 간선을 선택합니다.

3. 선택한 간선으로부터 연결된 정점을 최소 신장 트리에 추가합니다.

4. 추가한 정점과 연결된 간선 중에서 가장 작은 가중치를 가진 간선을 선택합니다.

5. 위의 과정을 반복하여 모든 정점을 최소 신장 트리에 추가할 때까지 진행합니다.

예시

프림 알고리즘의 구현 예시를 살펴보겠습니다

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

class Edge {
    int source;
    int destination;
    int weight;

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

class PrimMST {
    int vertices;
    List<List<Edge>> adjacencyList;

    public PrimMST(int vertices) {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination, int weight) {
        Edge edge = new Edge(source, destination, weight);
        adjacencyList.get(source).add(edge);
        adjacencyList.get(destination).add(edge);
    }

    public void findMinimumSpanningTree() {
        boolean[] visited = new boolean[vertices];
        PriorityQueue<Edge> minHeap = new PriorityQueue<>((e1, e2) -> e1.weight - e2.weight);

        // 임의의 시작 정점 선택
        int startVertex = 0;
        visited[startVertex] = true;

        // 시작 정점과 연결된 간선을 우선순위 큐에 추가
        for (Edge edge : adjacencyList.get(startVertex)) {
            minHeap.offer(edge);
        }

        while (!minHeap.isEmpty()) {
            // 가장 작은 가중치를 가진 간선 선택
            Edge minEdge = minHeap.poll();
            int source = minEdge.source;
            int destination = minEdge.destination;
            int weight = minEdge.weight;

            // 이미 방문한 정점인 경우 건너뛰기
            if (visited[source] && visited[destination]) {
                continue;
            }

            // 최소 신장 트리에 간선 추가
            System.out.println(source + " - " + destination + " : " + weight);

            // 선택한 간선의 도착 정점을 방문 처리하고, 해당 정점과 연결된 간선을 우선순위 큐에 추가
            if (!visited[destination]) {
                visited[destination] = true;
                for (Edge edge : adjacencyList.get(destination)) {
                    minHeap.offer(edge);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int vertices = 5;
        PrimMST mst = new PrimMST(vertices);

        mst.addEdge(0, 1, 2);
        mst.addEdge(0, 3, 6);
        mst.addEdge(1, 2, 3);
        mst.addEdge(1, 3, 8);
        mst.addEdge(1, 4, 5);
        mst.addEdge(2, 4, 7);
        mst.addEdge(3, 4, 9);

        mst.findMinimumSpanningTree();
    }
}

위의 코드는 프림 알고리즘을 사용하여 최소 신장 트리를 구하는 예시입니다. 코드를 간단히 설명하면 다음과 같습니다.

• Edge 클래스는 간선을 나타내는 클래스로, 시작 정점(source), 도착 정점(destination), 가중치(weight)를 가지고 있습니다.

• PrimMST 클래스는 프림 알고리즘을 구현한 클래스로, 정점의 개수(vertices)와 인접 리스트(adjacencyList)를 가지고 있습니다.

• addEdge 메서드를 사용하여 간선을 추가할 수 있습니다.

• findMinimumSpanningTree 메서드는 프림 알고리즘을 실행하여 최소 신장 트리를 찾습니다.

  • visited 배열을 사용하여 방문한 정점을 표시합니다.

  • minHeap 우선순위 큐를 사용하여 가장 작은 가중치를 가진 간선을 선택합니다.

  • 시작 정점을 선택하고, 해당 정점과 연결된 간선을 우선순위 큐에 추가합니다.

  • 우선순위 큐가 빌 때까지 가장 작은 가중치를 가진 간선을 선택하여 최소 신장 트리에 추가하고, 해당 정점과 연결된 간선을 우선순위 큐에 추가합니다.

• main 메서드에서 예시 그래프를 생성하고 findMinimumSpanningTree 메서드를 호출하여 최소 신장 트리를 출력합니다.

실행 결과는 다음과 같습니다.

0 - 1 : 2
1 - 2 : 3
0 - 3 : 6
1 - 4 : 5

위의 예시 그래프에서 생성된 최소 신장 트리의 간선들이 출력되었습니다. 각 간선은 시작 정점, 도착 정점, 가중치로 표시되며, 모든 정점을 포함하면서 사이클을 형성하지 않는 최소 신장 트리가 생성되었습니다.