Java에서 Kruskal 알고리즘을 구현하는 방법-java지도 시간-php.cn

Java에서 Kruskal 알고리즘을 구현하는 방법

王林

풀어 주다： 2023-05-11 22:19:04

앞으로

843명이 탐색했습니다.

소개

최소 신장 트리를 구성하는 또 다른 알고리즘, 즉 Kruskal 알고리즘이 있습니다. 그래프 G=(V, E)를 무방향 연결 가중 그래프, V={1,2,...n}으로 가정합니다. 최소 스패닝 트리 트리 T = (V, TE), 트리의 초기 상태는 n개의 노드만 있고 가장자리가 없는 연결되지 않은 그래프입니다. T = (V, {}) Kruskal의 알고리즘은 이러한 n개의 노드를 n개의 격리된 노드로 처리합니다. 연결된 지점. 먼저 모든 가장자리를 가중치에 따라 작은 것부터 큰 것까지 정렬한 다음 T에서 선택할 가장자리의 수가 n-1보다 작으면 다음과 같이 탐욕스러운 선택을 합니다. 가장자리(i,j)를 선택합니다. 에지 세트 E에서 가장 작은 가중치를 사용하여 에지 세트 TE에 에지 (i, j)를 추가해도 사이클이 생성되지 않으면 에지 세트 TE에 에지 (i, j)를 추가합니다. 즉, 에지 (i)를 사용합니다. , j) 두 가지를 연결된 가지로 병합합니다. 그렇지 않으면 다음으로 가장 짧은 가장자리를 계속 선택합니다. 집합 E에서 간선(i, j)을 삭제하고 T의 모든 노드가 동일한 연결된 가지에 있을 때까지 위의 욕심쟁이 선택을 계속합니다. 이때 선택된 n-1개의 간선은 정확히 그래프 G의 최소 스패닝 트리 T를 구성합니다.

Kruskal 알고리즘은 집합을 사용하여 결합하려는 가장자리의 시작점과 끝점이 모두 T 집합에 있으면 루프가 형성된다는 결론을 내릴 수 있는 매우 현명한 방법을 사용합니다. 변경된 두 노드는 동일한 세트에 속할 수 없습니다.

알고리즘 단계

1 초기화. 모든 간선을 가중치의 오름차순으로 정렬하고 각 노드 세트 번호를 고유한 번호로 초기화합니다.

2 정렬된 순서대로 가중치가 가장 작은 모서리(u, v)를 선택합니다.

3 노드 u와 v가 두 개의 서로 다른 연결된 가지에 속하는 경우 가장자리 세트 TE에 가장자리(u, v)를 추가하고 연결된 두 가지를 병합합니다.

4 선택한 모서리 수가 n-1보다 작으면 2단계로 이동하고, 그렇지 않으면 알고리즘이 종료됩니다.

1. 구성된 그림

Java에서 Kruskal 알고리즘을 구현하는 방법

2.Code

package graph.kruskal;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Kruskal {
    static final int N = 100;
    static int fa[] = new int[N];
    static int n;
    static int m;
 
    static Edge e[] = new Edge[N * N];
    static List<Edge> edgeList = new ArrayList();
 
    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }
 
    // 初始化集合号为自身
    static void Init(int n) {
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }
 
    // 合并
    static int Merge(int a, int b) {
        int p = fa[a];
        int q = fa[b];
        if (p == q) return 0;
        for (int i = 1; i <= n; i++) { // 检查所有结点，把集合号是 q 的改为 p
            if (fa[i] == q)
                fa[i] = p; // a 的集合号赋值给 b 集合号
        }
        return 1;
    }
 
    // 求最小生成树
    static int Kruskal(int n) {
        int ans = 0;
        Collections.sort(edgeList);
        for (int i = 0; i < m; i++)
            if (Merge(edgeList.get(i).u, edgeList.get(i).v) == 1) {
                ans += edgeList.get(i).w;
                n--;
                if (n == 1)//n-1次合并算法结束
                    return ans;
            }
        return 0;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        Init(n);
        for (int i = 1; i <= m; i++) {
            e[i].u = scanner.nextInt();
            e[i].v = scanner.nextInt();
            e[i].w = scanner.nextInt();
            edgeList.add(e[i]);
        }
        System.out.println("最小的花费是：" + Kruskal(n));
    }
}
 
class Edge implements Comparable {
    int u;
    int w;
    int v;
 
    @Override
    public int compareTo(Object o) {
        if (this.w > ((Edge) o).w) {
            return 1;
        } else if (this.w == ((Edge) o).w) {
            return 0;
        } else {
            return -1;
        }
    }
}

로그인 후 복사