java_그래프 구현_22.07.01(day22)

 

 

 

 

 

package datastructure.chap11;

// 정점 설계 [보관할 데이터를 담을 공간이라고 생각하면 된다.]

public class Vertex {

    private int id; // 정점 고유 번호
    private String data; //정점에 저장할 데이터
    private boolean visitFlag; // 정점방문 여부

    public Vertex(String data) {
        this.data = data;
        this.id = -1;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public boolean isVisitFlag() {
        return visitFlag;
    }

    public void setVisitFlag(boolean visitFlag) {
        this.visitFlag = visitFlag;
    }
}

 

 

package datastructure.chap11;

// 탐색에 초점을 맞춘 알고리즘
// 인접행렬 방식 그래프 구현 - 2차원 배열
public class GrapMatrix {

    // 배열을 쓰기 때문에 크기가 고정되어 있을수 밖에 없다. - 단점
    // 탐색시 메모리활용이 효율적이다. - 장점

    // 최대 정점 개수
    public static final int MAX = 50;

    //그래프의 인접방향을 저장할 인접 행렬
    private int[][] adjMatrix;

    //정점들을 모아둘 배열
    private Vertex[] vertices;

    //현재 그래프에 저장되어 있는 정점의 수 [실제 들어있는 수]
    private int numOfVertice;

    public GrapMatrix(){
        adjMatrix = new int[MAX][MAX];
        vertices = new Vertex[MAX];
    }

    // 그래프에 정점을 추가하는 메서드
    public void addVertex(Vertex v){
        // 정점 객체에 id부여 0부터 순차적 증가 [아이디를 인접행렬의 인덱스와 일치시키는 중]
        v.setId(numOfVertice);

        // 정점 배열에 추가
        vertices[numOfVertice++] = v;
    }

    // 간선 연결하기 (무방향 그래프)
    public void addEdge(Vertex departure, Vertex destination) {

        // 인접 행렬에 연결정보 저장
        adjMatrix[departure.getId()][destination.getId()] = 1;
        adjMatrix[destination.getId()][departure.getId()] = 1;
    }

    // 인접 행렬 출력
    public void showGraph() {
        System.out.print("    ");
        for (int i = 0; i < numOfVertice; i++) {
            System.out.print(vertices[i].getData() + " ");
        }
        System.out.println();

        for (int i = 0; i < numOfVertice; i++) {
            System.out.printf("%s | ", vertices[i].getData());
            for (int j = 0; j < numOfVertice; j++) {
                System.out.printf("%d ", adjMatrix[i][j]);
            }
            System.out.println();
        }
    }
}

 

package datastructure.chap11;

public class GraphTest {
    public static void main(String[] args) {
        // 그래프 생성
        GraphList gl = new GraphList();

        // 정점 생성
        Vertex A = new Vertex("A");
        Vertex B = new Vertex("B");
        Vertex C = new Vertex("C");
        Vertex D = new Vertex("D");
        Vertex E = new Vertex("E");

        // 정점 그래프에 추가
        gl.addVertex(A);
        gl.addVertex(B);
        gl.addVertex(C);
        gl.addVertex(D);
        gl.addVertex(E);

        // 정점들을 간선으로 연결
        gl.addEdge(A,B);
        gl.addEdge(B,E);
        gl.addEdge(E,D);
        gl.addEdge(B,C);

        //그래프 출력
        gl.showGraph();
    }
}

 

 

 

 

 

 

package datastructure.chap11;

// 탐색에 초점을 맞춘 알고리즘
// 인접행렬 방식 그래프 구현 - 2차원 배열
public class GrapMatrix {

    // 배열을 쓰기 때문에 크기가 고정되어 있을수 밖에 없다. - 단점
    // 탐색시 메모리활용이 효율적이다. - 장점

    // 최대 정점 개수
    public static final int MAX = 50;

    //그래프의 인접방향을 저장할 인접 행렬
    private int[][] adjMatrix;

    //정점들을 모아둘 배열
    private Vertex[] vertices;

    //현재 그래프에 저장되어 있는 정점의 수 [실제 들어있는 수]
    private int numOfVertice;

    public GrapMatrix(){
        adjMatrix = new int[MAX][MAX];
        vertices = new Vertex[MAX];
    }

    // 그래프에 정점을 추가하는 메서드
    public void addVertex(Vertex v){
        // 정점 객체에 id부여 0부터 순차적 증가 [아이디를 인접행렬의 인덱스와 일치시키는 중]
        v.setId(numOfVertice);

        // 정점 배열에 추가
        vertices[numOfVertice++] = v;
    }

    // 간선 연결하기 (무방향 그래프)
    public void addEdge(Vertex departure, Vertex destination) {

        // 인접 행렬에 연결정보 저장
        adjMatrix[departure.getId()][destination.getId()] = 1;
        adjMatrix[destination.getId()][departure.getId()] = 1;
    }

    // 인접 행렬 출력
    public void showGraph() {
        System.out.print("    ");
        for (int i = 0; i < numOfVertice; i++) {
            System.out.print(vertices[i].getData() + " ");
        }
        System.out.println();

        for (int i = 0; i < numOfVertice; i++) {
            System.out.printf("%s | ", vertices[i].getData());
            for (int j = 0; j < numOfVertice; j++) {
                System.out.printf("%d ", adjMatrix[i][j]);
            }
            System.out.println();
        }
    }
}

 

package datastructure.chap11;

public class MatrixTest {
    public static void main(String[] args) {

        // 그래프 생성
        GrapMatrix gm = new GrapMatrix();

        // 정점 생성
        Vertex A = new Vertex("A");
        Vertex B = new Vertex("B");
        Vertex C = new Vertex("C");
        Vertex D = new Vertex("D");
        Vertex E = new Vertex("E");

        // 정점 그래프에 추가
        gm.addVertex(A);
        gm.addVertex(B);
        gm.addVertex(C);
        gm.addVertex(D);
        gm.addVertex(E);

        // 정점들을 간선으로 연결
        gm.addEdge(A,B);
        gm.addEdge(B,E);
        gm.addEdge(E,D);
        gm.addEdge(B,C);

        //그래프 출력
        gm.showGraph();
    }
}