그래프

그래프(Graph)

정점과 간선으로 이루어진 자료구조

- 연결된 정점간의 관계를 표현 할 수 있는 자료구조

그래프의 용도

- 지하철 노선도, 통신 네트워크,.... 

 

정점(Vertex) : 각 노드 
간선(Edge) : 노드와 노드를 연결하는 선(link, branch)
인접 정점(Adjacent vertex) : 가선 하나를 두고 바로 연결된 정점 
정점의 차수(Degree) 
- 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
진입 차수(In-degree) : 방향 그래프에서 외부에서 오는 간선의 수
진출 차수(Out-degree) : 방향 그래프에서 외부로 나가는 간선의 수

경로 길이(Path length) : 경로를 구성하는데 사용된 간선의 수
단순 경로(Simple path) : 경로 중에서 반복되는 정점이 없는 경우
사이클(Cycle) : 단순 경로의 시작 정점과 끝 정점이 동일한 경우

 

 

 

 

그래프의 종류(1)
무방향 그래프
- 간선에 방향이 없는 그래프(양방향 이동 가능)
- 정검 A - B간선의 표현 : (A, B) = (B, A)
방향 그래프
- 간선에 방향이 있는 그래프(해당 방향으로만 이동 가능)
- 정점 A -> B 간선의 표현 : <A, B> != <B, A>

그래프의 종류(2)
가중치 그래프
- 간선에 값이 있는 그래프(이동 비용)
완전 그래프
- 모든 정점이 서로 연결되어 있는 그래프
- 정점이 N개일 경우, 간선의 수는 n(n-1) / 2개

그래프 탐색 -DFS
깊이 우선 탐색(Depth First Search)
- 각 노드에 방문했는지 여부를 체크할 배열과 스택 이용하여 구현

그래프 탐색 -BFS
너비 우선 탐색(Breath First Search)
- 각 노드에 방문 했는지 여부를 체크할 배열과 큐 이용하여 구현

그래프의 구현(1)

인접 행렬(Adjacency Matrix)
- 2차원 배열 이용

인접 행렬의 장단점
- 간선 정보의 확인과 업데이트가 빠름O(1)
- 인접 행렬을 위한 메모리 공간 차지

그래프의 구현(2)

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

인접 행렬 vs 인접 리스트

인접 행렬
- 노드의 개수가 적고 간선의 수가 많을 때 유리
인접 리스트
- 노드의 개수가 많고 간선의 수가 적을 때 유리

 

 

그래프 구현(인접 행렬)

 

class MyGraphMatrix {
    char[] vertices; // A B C D 담을 Data
    int[][] adjMat; // 2차원 인접 행렬
    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;
        }
        this.vertices[this.elemCnt++] = data; // A B C D  삽입
    }

    public void addEdge(int x, int y){ // 객체간 선 연결 ,  무 방향이니 둘다 1 로 해줌
        this.adjMat[x][y] = 1;
        this.adjMat[y][x] = 1;
    }
    public void directedEdge(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 : vertices){
            System.out.print(item + " "); // A B C D ~ ..
        }
        System.out.println();
        // 정점 개수 만큼 해당 인접행렬 Data 출력
        for (int i = 0; i < this.elemCnt; i++) {
            System.out.print(this.vertices[i] + " "); // 1 0 1 ~..
            for (int j = 0; j < elemCnt; j++) {
                System.out.print(this.adjMat[i][j] + " ");
            }
            System.out.println();
        }
    }
}

 

그래프 구현(인접 리스트)

class MyGraphList {
 char[] vertices;
 Node[] adjList;
 int eleCnt;

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

 public boolean isFull(){
     return this.eleCnt == this.vertices.length;
 }
    public void addVertex(char data){
     if(isFull()){
         System.out.println("Graph is Full!");
         return;
     }
        this.vertices[eleCnt++] = data;  // A B C D  삽입
    }

    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 static void main(String[ ] args)

 // Test code
        MyGraphMatrix graph = new MyGraphMatrix(4);

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

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

 

 

DFS(깊이 우선 탐색) Depth-First Search

• 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

class MyGraphMatrix2 extends MyGraphMatrix{
    public MyGraphMatrix2(int size){
        super(size);
    }
//    char[] vertices;  A B C D 담을 Data
//    int[][] adjMat;  2차원 인접 행렬
//    int elemCnt;  실제로 그래프의 정점의 개수가 몇 개 들어왔는지 새는
    public void dfs(int id){ // 방문 여부 배열, stack 자료구조
        boolean[] visited = new boolean[this.elemCnt]; // size는 실제로 들어있는 Node 수 만큼 (7)
        Stack<Integer> stack = new Stack<>();
        // 순회를 시작하려는 애 부터 stack에 넣기
        stack.push(id); // id = 0
        visited[id] = true; // visted[0] = true
        while (!stack.isEmpty()){ // stack이 비어있지 않는 동안
            int curId = stack.pop(); // stack에서 하나 꺼내고 출력
            System.out.print(this.vertices[curId] + " "); // 출력은 id에 해당하는 Node의 이름 출력 vertices[0] = A

            for (int i = this.elemCnt - 1; i >= 0; i--){ //   elemCnt = 7, i = 6
                if(this.adjMat[curId][i] == 1 && visited[i] == false){ // 만약 인접행렬의 해당 위치가 1이면 인접정점이 있고 방문한 적이 없다면,
                    stack.push(i); // 스택에 추가
                    visited[i] = true; // 방문 배열 체크
                }
            }
        }
        System.out.println();
    }

 

 

BFS(너비 우선 탐색) Breadth First Search

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 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();
    }
}