크 루스 카 르 최소 생 성 트 리

프 림 알고리즘 이 최소 생 성 트 리 를 구 하 는 것 과 달리 프 림 알고리즘 은 정점 을 중심 으로 하고 크 루 스 칼 알고리즘 은 변 을 중심 으로 한다.
프 림 알고리즘 최소 생 성 트 리 구하 기:https://blog.csdn.net/xindanding/article/details/90763065
크 루 스 칼 알고리즘 은 전제 가 있 습 니 다. 먼저 모든 변 을 가중치 상승 순 으로 배열 에 저장 한 다음 에 배열 요 소 를 옮 겨 다 니 며 회로 가 형성 되 지 않 으 면 이쪽 을 인쇄 해 야 합 니 다.
실현 절차:
 1. 인접 행렬 생 성 [0: 정점 에서 자신 에 게 끝 이 없다 는 뜻, 65535: 두 정점 사이 에 끝 이 없다 는 뜻]
  결 과 는 다음 과 같다.   0           1           65535   65535   5    1           0           2           65535   3    65535   2           0           3           65535    65535   65535   3           0           4    5          3            65535   4            0  
2. 실현:
그림 의 데이터 구조

public class Graph {
    String[] vertex = new String[5];    //        
    int[][] edge = new int[5][5];       //        

/ / get 생략, set 방법}

public class MinimunSpanningTree {

private static int edgelength = 0;     //                
    /**
     *                 
     *   ： 1.               2,    
     * @param g
     */
    public static void minimunSpan_kruskal(Graph g){
        Edge[] edges = new Edge[100];  //    100                    50       
        int adjvex[] = new int[100];  //    100                     ，             

//           
        for(int i = 0; i < adjvex.length; i++){
            adjvex[i] = 0;
        }

        //                       
        for(int i = 1; i < g.getVertex().length; i++){
            for(int j = 0; j < i; j++){    //        ，            ，           ，          
                if(g.getEdge()[i][j] > 0 && g.getEdge()[i][j] < 65535){
                    Edge edge = new Edge();
                    edge.setBegin(j);
                    edge.setEnd(i); //            ，                 
                    edge.setWeight(g.getEdge()[i][j]);  //           
                    insertIntoEdgeArray(edges, edge);
                }

            }
        }

        for(int k = 0; k < edgelength; k++){
            System.out.print("  ：" + edges[k].getWeight() + " ");
        }
        System.out.println();


        /**
         *             
         */

        for(int i = 0; i < edgelength; i++){
            Edge edge = edges[i];
            int n = findAdjvex(adjvex, edge.getBegin());  //                 
            int m = findAdjvex(adjvex, edge.getEnd());      //                 

            if(n != m){   //            findAdjvex      ，               
                adjvex[n] = m;
                System.out.println("     ： (" + edge.getBegin() + "," + edge.getEnd() + ")");
            }
        }
    }

    /**
     *                 
     * @param adjvex
     * @param point          
     * @return
     */
    private static int findAdjvex(int[] adjvex, int point){

        while(adjvex[point] != 0){
            point =  adjvex[point];
        }
        return point;
    }


    /**
     *            ,   
     * @param edges
     * @param edge
     */
    private static void insertIntoEdgeArray(Edge[] edges, Edge edge){

        /**
         *  edgelength           ,        edgelength  
         *    edgelength  0            
         */
        for(int i = 0; i <= edgelength; i++) {
            Edge arrayEdge = edges[i];
            if (arrayEdge == null) {
                edges[i] = edge;
                edgelength++;   //           1
                break;
            } else {

                //      i   
                if (arrayEdge.getWeight() >= edge.getWeight()) {
                    for (int j = edgelength; j > i; j--) {
                        edges[j] = edges[j - 1];
                    }
                    edges[i] = edge;
                    edgelength++;
                    break;
                }
            }

        }
    }
}

3. 결과
가중치: 1 가중치: 2 가중치: 3 가중치: 3 가중치: 4 가중치: 5  가중치 최소 변: (0, 1) 가중치 최소 변: (1, 2) 가중치 최소 변: (1, 4) 가중치 최소 변: (2, 3)