Graph (그래프)

1. 그래프(Graph)

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

  

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

2. 그래프의 종류 (1)

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

  

3. 그래프의 종류 (2)

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

4. 그래프 탐색 - DFS

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

5. 그래프 탐색 - BFS

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

6. 그래프의 구현 (1)

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

7. 그래프의 구현 (2)

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

(예제 : 그래프 구현)

// 비선형 자료구조 - 그래프
// 인접 행렬을 이용한 그래프 구현

import sun.security.rsa.RSAUtil;

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

        this.vertices[this.elemCnt++] = data;
    }

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