jyyoon

How will I serve the world?

6 분 소요

1. 그래프 자료구조

: 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이며, 한 노드로부터 다른 노드까지 가는 경우의 수가 1개 이상일 수 있음(Cyclic)

  • 정점(Vertex): 노드와 같은 말
  • 간선(Edge): 노드와 노드를 잇는 선(link, branch)
  • 인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점
  • 순회 방법: DFS(깊이 우선 탐색) / BFS(넓이 우선 탐색)

*트리(tree) 구조가 그래프의 한 종류이며, 방향성이 있고 계층적인 구조임. 두 노드간의 경로는 1개

2. 그래프 자료구조 구현방법

1) 행렬 이용

// vertex에 데이터들을 쭉 넣어놓고 행렬을 통해 간선을 표현함
class MyGraphMatrix {
    char[] vertices; // 노드 배열
    int[][] adjMat; // 간선 정보 행렬
    int elemCnt; // data가 들어온 개수

    public MyGraphMatrix() {
    }

    public MyGraphMatrix(int size) {
        this.vertices = new char[size];
        this.adjMat = new int[size][size];
        this.elemCnt = 0;
    }

    // 가득 찼는지 확인
    public boolean isFull() { // 실제 들어온 데이터 개수랑 노드 개수랑 같으면
        return this.elemCnt == this.vertices.length;
    }

    public void addVertex(char data) {
        if (isFull()) { // 가득 찼으면
            System.out.println("Full"); // 더이상 못채움
            return;
        }
        // 들어올 데이터를 elemCnt를 인덱스로 하는 노드에 넣기
        this.vertices[this.elemCnt++] = data;
    }

    // 간선 정보
    // 만약 1-2가 이어져있다면 (1,2), (2,1) 배열에 1 할당
    public void addEdge(int x, int y) {
        this.adjMat[x][y] = 1;
        this.adjMat[y][x] = 1;
    }
    // 방향이 있는 간선이라면 일방향만 넣기
    public void addDirectedEdge(int x, int y) {
        this.adjMat[x][y] = 1;
    }
    // 간선 삭제
    public void deleteEdge(int x, int y) {
        this.adjMat[x][y] = 0;
        this.adjMat[y][x] = 0;
    }
	// 방향이 있는 간선 삭제
    public void deleteDirectedEdge(int x, int y) {
        this.adjMat[x][y] = 0;
    }
	// 그래프 노드와 간선정보 출력
    public void printAdjacentMatrix() {
        System.out.print("  ");
        for (char item : this.vertices) {
            System.out.print(item + " ");
        }
        System.out.println();
		// 첫번째 노드부터 루프 돌면서
        for (int i = 0; i < this.elemCnt; i++) {
            System.out.print(this.vertices[i] + " "); 
            // 각 노드로 이어진 간선정보 표시
            for (int j = 0; j < this.elemCnt; j++) { 
                System.out.print(this.adjMat[i][j] + " ");
            }
            System.out.println();
        }
    }
}

public class Graph {
    public static void main(String[] args) {
        // 인접 행렬을 이용한 그래프 출력
        MyGraphMatrix grMatrix = new MyGraphMatrix(4);

        grMatrix.addVertex('A');
        grMatrix.addVertex('B');
        grMatrix.addVertex('C');
        grMatrix.addVertex('D');

        grMatrix.addEdge(0, 1);           // 출력정보
        grMatrix.addEdge(0, 2);             A B C D 
        grMatrix.addEdge(1, 2);           A 0 1 1 0 
        grMatrix.addEdge(1, 3);           B 1 0 1 1 
        grMatrix.addEdge(2, 3);           C 1 1 0 1 
        grMatrix.printAdjacentMatrix();   D 0 1 1 0 
    }
}

2) 링크드 리스트 이용

// 링크를 위한 노드 클래스
    class Node {
        int id;
        Structure.Node next;

    public Node(int id, Node next) {
        this.id = id;
        this.next = next;
    }
}

class MyGraphList {
    char[] vertices;
    Node[] adjList; // 간선 정보를 넣을 노드 배열
    int elemCnt; // 데이터 있는 노드 개수

    public MyGraphList() {}
    public MyGraphList(int size) {
        this.vertices = new char[size];
        this.adjList = new Node[size];
        this.elemCnt = 0;
    }

    public boolean isFull() {
        return this.elemCnt == this.vertices.length;
    }

    public void addVertex(char data) {
        if (isFull()) {
            System.out.println("Full");
            return;
        }
        this.vertices[elemCnt++] = data;
    }

    // 간선 정보 추가
    // 새 노드를 만들어서 기존에 x가 가리키고 있던 걸 가리키게 하고, 그 노드를 x가 가리키게 함
    // (y도 마찬가지로)
    public void addEdge(int x, int y) {
        this.adjList[x] = new Node(y, this.adjList[x]);
        this.adjList[y] = new Node(x, this.adjList[y]);
    }

    public void addDirectedEdge(int x, int y) {
        this.adjList[x] = new Node(y, this.adjList[x]);
    }

    public void printAdjacentList() {
        for (int i = 0; i < this.elemCnt; i++) {
            System.out.print(this.vertices[i] + ": ");

            Node cur = this.adjList[i];
            while (cur != null) {
                System.out.print(this.vertices[cur.id] + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    }
}

public class Graph {
    public static void main(String[] args) {
        // 인접 리스트를 이용한 그래프 출력
        MyGraphList grList = new MyGraphList(4);

        grList.addVertex('A');
        grList.addVertex('B');
        grList.addVertex('C');
        grList.addVertex('D');

        grList.addEdge(0, 1);        // 출력 정보
        grList.addEdge(0, 2);		A: C B 
        grList.addEdge(1, 2);		B: D C A 
        grList.addEdge(1, 3);		C: D B A 
        grList.addEdge(2, 3);		D: C B 
        grList.printAdjacentList();
    }
}

3. 순회

1) BFS(넓이 우선 탐색)

[준비 변수]

  • 노드 방문 여부를 체크할 배열
  • 큐

[구현 방법]

  • 시작점 큐에 넣기
  • 꺼내기
  • 인접 노드 큐에 넣기
  • 큐가 빌 때까지 반복
1. 배열을 활용한 bfs 순회
// 위에서 사용한 클래스에서 구현한다고 가정
class MyGraphMatrix {
    char[] vertices; // 노드 배열
    int[][] adjMat; // 간선 정보 행렬
    int elemCnt; // data가 들어온 개수

    public MyGraphMatrix() {
    }

    public MyGraphMatrix(int size) {
        this.vertices = new char[size];
        this.adjMat = new int[size][size];
        this.elemCnt = 0;
    }
}
// 넓이 우선 탐색
public void bfs(int start) {
    boolean[] visited = new boolean[this.elemCnt]; // 방문여부 체크할 배열
    Queue<Integer> queue = new LinkedList<>(); // 큐
    
    queue.offer(start); // 시작점 큐에 넣기
    visited[start] = true; // 방문 체크
    // 큐가 빌 때까지
    while(!queue.isEmpty()) {
        int curId = queue.poll(); // 하나 꺼내서
        System.out.print(this.vertices[curId] + " "); // 출력
        // 간선 정보 배열 돌면서
        for(int i = 0; i < this.elemCnt; i++) {
            // 간선이 연결되어 있고 방문을 안했을 경우
            if(this.adjMat[curId][i] == 1 && visited[i] == false) {
                queue.offer(i); // 큐에 넣기
                visited[i] = true; // 방문 체크
            }
        }
    }
}

2. 링크드리스트를 활용한 bfs 순회
// 링크를 위한 노드 클래스
    class Node {
        int id;
        Structure.Node next;

    public Node(int id, Node next) {
        this.id = id;
        this.next = next;
    }
}

class MyGraphList {
    char[] vertices;
    Node[] adjList; // 간선 정보를 넣을 노드 배열
    int elemCnt; // 데이터 있는 노드 개수

    public MyGraphList() {}
    public MyGraphList(int size) {
        this.vertices = new char[size];
        this.adjList = new Node[size];
        this.elemCnt = 0;
    }
}
// 넓이 우선 탐색
public void bfs(int start) {
    boolean[] visited = new boolean[elemCnt]; // 방문여부 체크할 배열
    Queue<Integer> queue = new LinkedList<>(); // 큐
    
    queue.offer(start); // 시작점 큐에 넣기
    visited[start] = true; // 방문 체크
    // 큐 빌 때까지
    while(!queue.isEmpty()) {
        int curId = queue.poll(); // 하나 꺼내서
        System.out.print(this.vertices[curId] + " "); // 출력
        // 이 노드를 cur에 넣고
        Node cur = this.adjList[curId];
        while(cur != null) { // 간선이 없을때까지, 즉 링크가 끊어질때까지
            if(visited[cur.id] == false) { // 방문을 하지 않은곳에
                queue.offer(cur.id); // 큐에 넣고
                visited[cur.id] = true; // 방문 체크
            }
            cur = cur.next; // 다음 노드로 이동
        }
    }
}

2) DFS(깊이 우선 탐색)

[준비 변수]

  • 노드 방문 여부를 체크할 배열
  • 스택

[구현 방법]

  • 시작점 스택에 넣기
  • 꺼내기
  • 인접 노드 스택에 넣기
  • 스택이 빌 때까지 반복

*DFS는 재귀함수로 구현이 가능하며, 코드가 더 깔끔한 장점이 있음

1. 배열을 활용한 dfs 순회
// 위에서 사용한 클래스에서 구현한다고 가정
class MyGraphMatrix {
    char[] vertices; // 노드 배열
    int[][] adjMat; // 간선 정보 행렬
    int elemCnt; // data가 들어온 개수

    public MyGraphMatrix() {
    }

    public MyGraphMatrix(int size) {
        this.vertices = new char[size];
        this.adjMat = new int[size][size];
        this.elemCnt = 0;
    }
}
// 깊이 우선 탐색
public void dfs(int start) {
    boolean[] visited = new boolean[elemCnt]; // 방문여부 체크할 배열
    Stack<Integer> stack = new Stack<>(); // 스택
    
    stack.push(start); // 시작점 스택에 넣기
    visited[start] = true; // 방문 체크
    
    while(!stack.isEmpty()) { // 스택이 빌 때까지
        int curId = stack.pop(); // 하나 꺼내서
        System.out.print(this.vertices[curId] + " "); // 출력
        // 간선 정보 배열 돌면서
        for(int i = 0; i < elemCnt; i++) {
            // 간선이 연결되어 있고 방문을 안했을 경우
            if(this.adjMat[curId][i] == 1 && visited[i] == false) {
                stack.push(i); // 스택에 넣기
                visited[i] = true; // 방문 체크
            }
        }
    }
}

2. 링크드리스트를 활용한 dfs 순회
// 링크를 위한 노드 클래스
    class Node {
        int id;
        Structure.Node next;

    public Node(int id, Node next) {
        this.id = id;
        this.next = next;
    }
}

class MyGraphList {
    char[] vertices;
    Node[] adjList; // 간선 정보를 넣을 노드 배열
    int elemCnt; // 데이터 있는 노드 개수

    public MyGraphList() {}
    public MyGraphList(int size) {
        this.vertices = new char[size];
        this.adjList = new Node[size];
        this.elemCnt = 0;
    }
}
// 깊이 우선 탐색
public void dfs(int start) {
    boolean[] visited = new boolean[elemCnt]; // 방문여부 체크할 배열
    Stack<Integer> stack = new Stack<>(); // 스택
    
    stack.push(start); // 시작점 스택에 넣기
    visited[start] = true; // 방문 체크
    // 스택 빌 때까지
    while(!stack.isEmpty()) {
        int curId = stack.pop(); // 하나 꺼내서
        System.out.print(this.vertices[curId] + " "); // 출력
        // 이 노드를 cur에 넣고
        Node cur = this.adjList[curId];
        while(cur != null) { // 간선이 없을때까지, 즉 링크가 끊어질때까지
            if(visited[cur.id] == false) { // 방문을 하지 않은곳에
                stack.push(cur.id); // 스택에 넣고
                visited[cur.id] = true; // 방문 체크
            }
            cur = cur.next; // 다음 노드로 이동
        }
    }
}

마지막 수정일시: 2022-06-15 03:20

댓글남기기

참고

SpringSecurity - 기본

3 분 소요

Spring Security는 Spring 프레임워크에서 제공하는 인증, 인가를 쉽게 처리할 수 있는 방식을 Filter를 활용하여 제공한다.