📌 About

Kruskal algorithm에 대해서 설명하기 전에 spanning tree에 대해서 우선 알아야 한다. Spanning tree란 graph의 최소 연결 부분 그래프로 간선의 수가 가장 적기 때문에 V개의 정점이 있다면 정점 E = V - 1이 된다. 또한 graph 내에서 사이클을 형성하면 안된다. 여기서 MST라는 개념이 나오는데 이는 spanning tree 중에서는 가중치의 합이 가장 적은 것을 의미한다.

Kruskal algorithm은 MST를 구하기 위한 algorithm이다. Graph의 간선들을 오름차순으로 정렬하고 차례대로 graph에 추가한다. 이 때 추가되는 간선 때문에 cycle이 형성되면 해당 간선은 추가하지 않는다.

Cycle을 이루는지 확인하는 방법은 union-find를 이용하는 것이다. 이는 집합을 사용하는 것인데 처음에는 모든 정점이 자신으로만 이루어진 집합에 속한다. 또한 각각의 집합은 포함된 원소들 중에 하나의 정점을 root으로 한다. 하나의 간선(두 개의 정점)의 cycle 생성 여부를 판단할 때 두 정점이 포함된 집합의 root를 확인한다. 확인한 두 root가 같으면 두 정점은 같은 집합에 있는 것이고 간선을 포함했을 때 cycle이 형성된다. 반대로 root가 다르면 다른 집합에 속한 것이기 때문에 간선을 추가하여도 cycle이 형성되지 않는다.

📌 Algorithm

Step 1. E개의 간선들을 오름차순으로 탐색한다.

Step 2. 탐색한 간선 양끝 정점의 root 정점을 확인한다.

• union-find의 find 함수를 통해 root 정점을 확인한다.

Step 3. 두 정점의 root 정점이 다르면 union 함수를 통해 간선을 MST에 추가한다.

Step 3-1. 간선 정보를 MST에 추가한다.

Step 3-2. 각 정점의 root 정점을 확인한다.

• Step 3-3. 두 root 정점 중 하나가 다른 하나를 root로 한다.

📌 Java Code

public class Kruskal {

    private final Queue<Edge> edges 
						= new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
    private final Map<Vertex, Vertex> roots = new HashMap<>();
    private final Map<Vertex, Map<Vertex, Integer>> graph = new HashMap<>();

    public Kruskal(List<Vertex> vertices, List<Edge> edges) {
        this.edges.addAll(edges);
        for (Vertex vertex : vertices) {
            roots.put(vertex, vertex);
            graph.put(vertex, new HashMap<>());
        }
    }

    public Map<Vertex, Map<Vertex, Integer>> run() {
        selectEdgesToMerge();
        return graph;
    }

    private void selectEdgesToMerge() {
        while (!edges.isEmpty()) {
            Edge edge = edges.poll();
            if (find(edge.vertexA).equals(edge.vertexB)) {
                graph.get(edge.vertexA).put(edge.vertexB, edge.weight);
                graph.get(edge.vertexB).put(edge.vertexA, edge.weight);
                union(edge.vertexA, edge.vertexB);
            }
        }
    }

    private void union(Vertex vertexA, Vertex vertexB) {
        vertexA = find(vertexA);
        vertexB = find(vertexB);
        if (vertexA.value < vertexB.value) roots.put(vertexB, vertexA);
        else roots.put(vertexA, vertexB);
    }

    private Vertex find(Vertex vertex) {
        Vertex root = roots.get(vertex);
        return root.equals(vertex) ? vertex : find(root);
    }
}

📌 Example

다음과 같은 graph가 있다.

Step 1. 간선들을 오름차순으로 탐색한다.

Vertex 1 - Vertex 2 - Weight 1

Vertex 2 - Vertex 3 - Weight 2

Vertex 3 - Vertex 1 - Weight 3

• 간선 {1, 2 → 1} 탐색

정점 1의 루트는 1이다.

정점 2의 루트는 2이다.

루트가 다르기 때문에 MST에 추가한다.

정점 2의 루트를 1로 한다.