2019 - 2020 - 1 실험 9 보고서

\ # 20182327 2019 - 2020 - 1 실험 9 보고서
과정: 반: 1823 이름: 조 천 호 학 번: 20182327 실험 교사: 왕 지 강 실험 날짜: 2019 년 12 월 2 일 필수 / 선택 과목: 필수
1. 실험 내용

(1) 초기 화: 화면 알림 (예 를 들 어 1 을 무 방향 그림 으로 입력 하고 2 를 유 방향 그림 으로 입력) 에 따라 무 방향 그림 과 유 방향 그림 (인접 행렬 로 도 사용 할 수 있 고 인접 표 로 도 사용 할 수 있 음) 을 초기 화 합 니 다. 그림 은 스스로 정의 해 야 합 니 다 (정점 개수, 변 개수, 먼저 초고 지 에 그림 을 그린 다음 에 정점 과 변 수 를 입력 하 는 것 을 권장 합 니 다) (2 점)

(2) 그림 의 옮 겨 다 니 기: 그림 과 방향 이 없 는 옮 겨 다 니 기 (깊이 와 넓이 우선 옮 겨 다 니 기) (4 분)

(3) 그림 에 대한 토폴로지 정렬 을 완성 하고 토폴로지 정렬 순 서 를 출력 하거나 이 그림 에 존재 하 는 링 (3 점)

을 출력 합 니 다.

(4) 그림 이 없 는 최소 생 성 트 리 (Prim 알고리즘 또는 Kruscal 알고리즘 모두 가능) 를 완성 하고 출력 (3 점)

(5) 그림 에 대한 단일 소스 의 최 단 경로 풀이 (디 제 스 트 라 알고리즘) (3 점)

를 완성 했다.
2. 실험 과정 과 결과

편집 그림:

import java.util.Scanner;
//  ，            
public class Graph9 {
//      
    int verNum;
//       
 int edgeNum;
 //             
Vertex[] verArray;
// Graph      ，      、    ，      。
 public Graph9() {
        Scanner scan = new Scanner(System.in);
        System.out.println("                ： (     0，     1)");
        int choose = scan.nextInt();
        System.out.println("            ：");
        verNum = scan.nextInt();
        edgeNum = scan.nextInt();
        verArray = new Vertex[verNum];
        System.out.println("          :");
        for (int i=0;i

옮 겨 다 니 기:

       
      import java.util.*;

/**
 *   java                    。
 */
public class GraphLoopTest {
    private Map> graph = new HashMap>();

    /**
     *       ：           。
     */
    public void initGraphData() {
//             
//          3
//        /   \
//       4     5
//      / \   / \
//     6  7  8  9
//      \ | / \ /
//        10   11
        graph.put("3", Arrays.asList("4", "5"));
        graph.put("4", Arrays.asList("3", "6", "7"));
        graph.put("5", Arrays.asList("3", "8", "9"));
        graph.put("6", Arrays.asList("4", "10"));
        graph.put("7", Arrays.asList("4", "10"));
        graph.put("8", Arrays.asList("5", "10", "11"));
        graph.put("9", Arrays.asList("5", "11"));
        graph.put("10", Arrays.asList("6", "7", "8"));
        graph.put("11", Arrays.asList("8", "9"));
    }

    /**
     *       (BFS, Breadth First Search)
     * BFS    (queue)       
     */
    private Queue queue = new LinkedList();
    private Map status = new HashMap();

    /**
     *    
     *
     * @param startPoint
     */
    public void BFSSearch(String startPoint) {
        //1.      queue；
        queue.add(startPoint);
        status.put(startPoint, false);
        bfsLoop();
    }

    private void bfsLoop() {
        //  1)  queue        ；         。
        String currentQueueHeader = queue.poll(); //  
        status.put(currentQueueHeader, true);
        System.out.println(currentQueueHeader);
        //  2)                ，    ，      queue 。
        List neighborPoints = graph.get(currentQueueHeader);
        for (String poinit : neighborPoints) {
            if (!status.getOrDefault(poinit, false)) { //    
                if (queue.contains(poinit)) continue;
                queue.add(poinit);
                status.put(poinit, false);
            }
        }
        if (!queue.isEmpty()) {  //           
            bfsLoop();
        }
    }

    private Stack stack = new Stack();
    public void DFSSearch(String startPoint) {
        stack.push(startPoint);
        status.put(startPoint, true);
        dfsLoop();
    }

    private void dfsLoop() {
        if(stack.empty()){
            return;
        }
        //      ，     
        String stackTopPoint = stack.peek();
        //  2)                ，    ，      queue 。
        List neighborPoints = graph.get(stackTopPoint);
        for (String point : neighborPoints) {
            if (!status.getOrDefault(point, false)) { //    
                stack.push(point);
                status.put(point, true);
                dfsLoop();
            }
        }
        String popPoint =  stack.pop();
        System.out.println(popPoint);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("     （1）      （0）");
        int choose = scan.nextInt();
        GraphLoopTest test = new GraphLoopTest();
        test.initGraphData();
        if(choose==0){
            System.out.println("       ：");
            test.BFSSearch("3");}
        if(choose==1){
            System.out.println("      ： ");
            test.DFSSearch("3");}

    }
}

prim 알고리즘:

    public class Prim {

    public static void PRIM(int [][] graph,int start,int n){
        int [][] mins=new int [n][2];
        for(int i=0;imins[j][1]){
                    minW=mins[j][1];
                    minV=j;
                }
            }
            mins[minV][1]=0;
            System.out.println("       "+i+"    =，  ="+minW);
            for(int j=0;j

디 제 스 트 라 알고리즘

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
public class DijstraAlgorithm {
    public static void main(String[] args) {
        int vertexNum = 5;
        char[] vertexs = new char[] { 'Z', 'T', 'H', 'N', 'B' };
        int[][] matrix = new int[][] { { 0, 10, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 5 },
                { Integer.MAX_VALUE / 2, 0, 1, Integer.MAX_VALUE / 2, 2 },
                { Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 0, 4, Integer.MAX_VALUE / 2 },
                { 7, Integer.MAX_VALUE / 2, 6, 0, Integer.MAX_VALUE / 2 },
                { Integer.MAX_VALUE / 2, 3, 9, 2, 0 } }; // matrix[i][j] 0  i==j,matrix[i][j] Integer.MAX_VALUE/2           ,        
        Graph g = new Graph(vertexNum, vertexs, matrix);
        Scanner sc = new Scanner(System.in);
        int srcIndex;
        do{
            System.out.print("       (0~4):");
            srcIndex = sc.nextInt();
        }while(srcIndex < 0 || srcIndex > 4);
        System.out.println(g.vertexs[srcIndex] + "    ");
        Info info = dijkstra(g, srcIndex); //       srcIndex       
        for(int i : info.pathSerials){
            System.out.print(g.vertexs[i] + " ");
        }
        System.out.println();
        int index = 0;
        for(int[] path : info.paths){
            for(int i : path){
                System.out.print(g.vertexs[i]);
            }
            System.out.println(": " + info.distances[index++]);
        }
        sc.close();
    }
    //        (Dijkstra)    vertex[srcIndex]                 
    public static Info dijkstra(Graph g, int srcIndex) {
        if(srcIndex < 0 || srcIndex >= g.vertexNum){
            return null;
        }
        int[] pathSerials = new int[g.vertexNum]; // pathSerials[i]        i     (  P(srcIndex,j)={V(srcIndex)...Vk...Vs...Vj}    srcIndex j     ,  P(srcIndex,j)=P(srcIndex,k)+P(k,s)+P(s,j))
        int[] path = new int[g.vertexNum]; // path[i]        i(i vertexs    )        i     
        int index = 0;
        pathSerials[index] = srcIndex; //        
        g.visited[srcIndex] = true; //            
        Arrays.fill(path, -1); // -1          
        int[] distances = new int[g.vertexNum]; // distances[i]        i(i vertexs    )         
        for (int i = 0; i < g.vertexNum; i++) {
            //    distances           
            distances[i] = g.matrix[srcIndex][i];
        }
        int minIndex = srcIndex;
        while (minIndex != -1) { //                 
            index++;
            for (int i = 0; i < g.vertexNum; i++) {
                if (!g.visited[i]) { //                          
                    //                   distances[i]  (      minIndex distances[minIndex] minIndex   i  ) (  minIndex        i    distances[i])        
                    distances[i] = Math.min(distances[i], distances[minIndex] + g.matrix[minIndex][i]);
                    //       i distances[i]        minIndex,   i    minIndex,    
                    if(distances[i] == distances[minIndex] + g.matrix[minIndex][i] && distances[i] != Integer.MAX_VALUE / 2){ // distances[i] != Integer.MAX_VALUE / 2      ，     
                        path[i] = minIndex;
                    }
                }
            }
            minIndex = indexOf(g, distances); //        
            if(minIndex == -1){
                break;
            }
            pathSerials[index] = minIndex; //                   
            g.visited[minIndex] = true;
        }
        return new Info(distances, pathSerials, getPathOfAll(path, pathSerials));
    }
    //                                 
    public static int indexOf(Graph g, int[] distances) {
        int min = Integer.MAX_VALUE / 3;
        int minIndex = -1; //     distances       (-1       )--                     
        for(int i = 0; i < g.vertexNum; i++){
            if(!g.visited[i]){ //   i              
                if(distances[i] < min){
                    min = distances[i];
                    minIndex = i;
                }
            }
        }
        return minIndex;
    }
    //       i       i     (     vertexs     )
    public static int[] getPath(int[] path, int i){
        Stack s = new Stack();
        s.push(i);
        int pre = path[i];
        while(pre != -1){
            s.push(pre);
            pre = path[pre];
        }
        int size = s.size();
        int[] pathOfVertex = new int[size];
        while(!s.isEmpty()){
            pathOfVertex[size - s.size()] = s.pop();
        }
        return pathOfVertex;
    }
    public static ArrayList getPathOfAll(int[] path, int[] pathSerials){
        ArrayList paths = new ArrayList();
        for(int i = 0; i < pathSerials.length; i++){
            paths.add(getPath(path, i));
        }
        return paths;
    }
    public static class Graph{
        private int vertexNum;
        private char[] vertexs;
        private int[][] matrix;
        private boolean visited[];

        public Graph(int vertexNum, char[] vertexs, int[][] matrix){
            this.vertexNum = vertexNum;
            this.vertexs = vertexs;
            this.matrix = matrix;
            visited = new boolean[vertexNum];
        }
    }
    public static class Info{
        private int[] distances; //             
        private int[] pathSerials; //         
        private ArrayList paths; //                 
        public Info(int[] distances, int[] pathSerials, ArrayList paths) {
            this.distances = distances;
            this.pathSerials = pathSerials;
            this.paths = paths;
        }

    }
}

3. 실험 과정 에서 발생 하 는 문제 와 해결 과정

문제 1: 각종 빈 지침 오류

문제 해결 방법: 드라이버 코드 를 다시 편집 하고 호출 이 초기 화 되 었 는 지 확인 합 니 다.

기타 (깨 달 음, 사고 등)
종합 실천 은 정말 어렵다. 한편 으로 는 안 드 로 이 드 가 생각 하면 서 하나 가 될 것 같다.