クルーズアルゴリズム

*MST(Minimum Spanning Tree)

≪ツリーの生成｜Generate Tree｜oem_src≫:グラフィック内のすべてのノードを含むツリー

≪最小生成ツリー｜Minimum Generation Tree｜oem_src≫:生成ツリーで使用される幹線重み付けが最小のツリー

*クルーズアルゴリズム(Kruskalアルゴリズム)

通信、道路網、流通網の長さ、構築コスト、伝送時間等のみを最小化する.

Union Findアルゴリズムの適用(認識サイクル)

無方向性、重み付けグラフィックで使用

*問題の状況

この図では、全てのノードを含む木となるために必要な幹線数が必要な幹線数

よりも多くなる.

幹線の重み付け中小幹線を点検し、故障がなければ接続する.

何が神経症ですか.

サイクルなし

サイクルあれば

整理して、あるノードから出発して、自分の体に戻れるものをサイクと言います.
MSTの作成中(クルーズアルゴリズムの実行時)に幹線を追加するSickelが現れた場合,前期のいずれかのグループが部分的にMSTを作成していたと考えられる.そのため、この幹線を増やすには不要な費用の増加を排除しなければならない.

N個のノードが存在する場合、すべてのノードを含むツリーを作成する最小幹線数はN−1である.

したがって、N-1本の幹線を接続すると、幹線は追加されません.
Step 1ノードと重みをオブジェクトとして管理する.

Step 2本線の重み付けを基準に昇順ソートを行います.

本線の重み付けを最小にするために、幹線の重み付け値が小さいことから検査を行い、故障がなければノードを接続する.

Step 3順番に並べられた接続情報をブラウズし、幹線を追加しても故障がなければ幹線を接続する.
N-1本を追加するまでStep 4本線を追加

import java.util.*;

public class KruskalAlgorithm{

    static int[] parent = new int[9];

    public static int findParent(int search){
        if(parent[search] == search) return search;

        return parent[search] = findParent(parent[search]);
    }

    public static void unionParent(int a, int b){
        int aParent = findParent(a);
        int bParent = findParent(b);

        parent[aParent] = bParent;
    }

    static class Edge implements Comparable<Edge>{
        int node1;
        int node2;
        int weight;

        public Edge(int node1, int node2, int weight){
            this.node1 = node1;
            this.node2 = node2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args){
        for(int i = 1 ; i < 9; i++){
            parent[i] = i;
        }

        int edgeCount = 0;
        List<Edge> result = new ArrayList<>();

        //step1
        List<Edge> arr = new ArrayList<>();
        arr.add(new Edge(1,2,2));
        arr.add(new Edge(1,4,4));
        arr.add(new Edge(1,4,3));
        arr.add(new Edge(2,4,4));
        arr.add(new Edge(2,3,2));
        arr.add(new Edge(2,5,6));
        arr.add(new Edge(5,3,1));
        arr.add(new Edge(3,6,4));

        //step2
        Collections.sort(arr);

        //stap3
        for(Edge e : arr){
            if(findParent(e.node1) != findParent(e.node2)){
                unionParent(e.node1,e.node2);
                result.add(new Edge(e.node1,e.node2,e.weight));
                edgeCount++;
            }
            if(edgeCount == 5) break;
        }

        //result
        for(Edge e : result){
            System.out.println("node1 : " + e.node1 + " node2 : " + e.node2 + " weight : " + e.weight);
        }

    }
}

この文章はこのブログの勉強に基づいて書かれた.
https://m.blog.naver.com/ndb796/221230967614