그래프

wellsbabo·2023년 4월 6일
0

자료구조

목록 보기
4/7

그래프

개요

  • 정점과 간선으로 이루어진 자료구조 (Cyclic)
    - 연결된 정점간의 관계를 표현할 수 있는 자료구조
    • 용도: 지하철 노선도, 통신 네트워크...

구조

  • 정점(Vertex): 각 노드
  • 간선(Edge): 노드와 노드를 연결하는 선 (link, branch)
  • 인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점
  • 정점의 차수(Degree):
    무방향 그래프에서 하나의 정점에 인접한 정점의 수
    무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
  • 진입 차수(In-degree): 방향 그래프에서 외부에서 오는 간선의 수
  • 진출 차수(Out-degree): 방향 그래프에서 외부로 나가는 간선의 수
  • 경로 길이(Path length): 경로를 구성하는데 사용된 간선의 수
  • 단순 경로(Simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우

그래프와 트리의 차이

그래프의 종류

1) 무방향 그래프

  • 간선에 방향이 없는 그래프 (양방향 이동 가능)
  • 정점 A-B 간선의 표현: (A,B) = (B,A)
    2) 방향 그래프
  • 간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능)
  • 정점 A->B 간선의 표현: <A,B> != <B,A>
    3) 가중치 그래프
  • 간선에 값이 있는 그래프 (이동 비용)
    4) 완전 그래프
  • 모든 정점이 서로 연결되어 있는 그래프
  • 정점이 N개일 경우, 간선의 수는 n(n-1)/2개

그래프 탐색

  • 각 노드에 방문했는지 체크할 배열과 스택을 이용하여 구현
  • 순서
    1) 방문 체크를 위한 배열 생성
    2) 스택 생성
    3) 스택에 방문한 노드를 추가
    4) 스택에서 꺼내면서 출력하고, 다음에 방문할 수 있는 노드들을 스택에 추가 (스택에 추가하면서 방문 배열을 1로 수정. 이미 배열이 1인 노드는 스택에 추가하지 않음)
  • 각 노드에 방문했는지 체크할 배열과 큐를 이용하여 구현
  • 순서는 DFS와 거의 동일하지만 큐라서 나오는 순서가 다름

그래프 구현

인접행렬

  • 2차원 배열 이용
  • 장점: 간선 정보의 확인과 업데이트가 빠르다. O(1)
  • 단점: 인접 행렬을 위한 메모리 공간을 차지한다

인접 리스트

  • 연결리스트 이용
  • 장점: 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제 빠름
  • 단점: 간선 정보 확인이 상대적으로 오래 걸림

인접 행렬 vs 인접 리스트

인접 행렬

노드의 개수가 적고 간선의 수가 많을 때 유리하다

인접 리스트

노드의 개수가 많고 간선의 수가 적을 때 유리하다


인접행렬 소스코드

// 인접 행렬을 이용한 그래프 구현

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class MyGraphMatrix {
    char[] vertices;    //정점(노드)
    int[][] adjMat; //간선
    int elemCnt;    //현재 정점의 개수

    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("Graph is full!");
            return;
        }
        //현재 elemCnt에 data를 넣고 elemCnt의 값을 +1
        this.vertices[this.elemCnt++] = data;
    }

    //x와 y사이에 간선을 추가해주는 메소드
    public void addEdge(int x, int y){
        //무방향 그래프일때는 이렇게 (x,y) (y,x) 2가지의 간선을 추가해주어야 한다
        this.adjMat[x][y] = 1;
        this.adjMat[y][x] = 1;
    }

    public void addDirectedEdge(int x, int y){
        //방향 그래프일때는 입력받은 방향대로 1가지의 간선만 추가해주면 된다
        this.adjMat[x][y] = 1;
    }

    //x와 y 사이의 간선을 삭제해주는 메소드
    public void deleteEdge(int x, int y){
        //무방향 그래프일때는 2가지를 삭제
        this.adjMat[x][y] = 0;
        this.adjMat[y][x] = 0;
    }

    public void deleteDirectedEdge(int x, int y){
        //방향 그래프일때는 1가지 삭제
        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();
        }
    }

    //DFS 깊이우선탐색
    //id부터 탐색시작
    public void dfs(int id){
        boolean[] visited = new boolean[this.elemCnt];
        Stack<Integer> stack = new Stack<>();

        //스택에 탐색을 시작할 값 넣고 시작
        stack.push(id);
        visited[id] = true;

        while(!stack.isEmpty()){    //스택이 빌떄까지
            int curId = stack.pop();    //값을 뽑고
            System.out.print(this.vertices[curId] + " ");

            for (int i = this.elemCnt - 1; i >= 0; i--) {   //방문을 어디서부터 할지 기준에 따라 초기값 설정
                if(this.adjMat[curId][i] == 1 && visited[i] == false){  //인접행렬이고 아직 방문을 안했으면
                    stack.push(i);  //스택에 집어넣음
                    visited[i] = true;  //스택에 넣으면서 방문 체크
                }
            }
        }
        System.out.println();
    }

    //BFS 넓이우선탐색
    //id부터 탐색시작
    public void bfs(int id){
        boolean[] visited = new boolean[this.elemCnt];
        Queue<Integer> queue = new LinkedList<>();

        //큐에 탐색을 시작할 값 넣고 시작
        queue.offer(id);
        visited[id] = true;

        while(!queue.isEmpty()){    //큐가 빌때까지
            int curId = queue.poll();   //값을 뽑고
            System.out.print(this.vertices[curId] + " ");

            for (int i = this.elemCnt - 1; i >= 0; i--) {   //방문을 어디서부터 할지 기준에 따라 초기값 설정
                if(this.adjMat[curId][i] == 1 && visited[i] == false){  //인접행렬이고 아직 방문을 안했으면
                    queue.offer(i); //큐에 집어넣음
                    visited[i] = true;  //큐에 넣으면서 방문 체크
                }
            }
        }
        System.out.println();
    }

}

public class Main {
    public static void main(String[] args) {
        // Test code
        MyGraphMatrix graph = new MyGraphMatrix(7);

        graph.addVertex('A');   // 0
        graph.addVertex('B');   // 1
        graph.addVertex('C');   // 2
        graph.addVertex('D');   // 3
        graph.addVertex('E');   // 4
        graph.addVertex('F');   // 5
        graph.addVertex('G');   // 6

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 6);
        graph.addEdge(5, 6);
        graph.printAdjacentMatrix();

        graph.dfs(0);
        graph.bfs(0);
    }
}

0개의 댓글