[자료구조] 그래프(Graph)

그래프

• 개념

  • 단순히(node, N)와 그 노드를 연결하는 간선(edge, E)을 하나로 모아 놓은 자료구조
  • 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조

• 용어

  • 정점(vertex): 위치라는 개념. (node 라고도 부름)
  • 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
  • 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
  • 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
  • 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
  • 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
  • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

• 특징

  • 그래프는 네트워크 모델이다.
  • 2개 이상의 경로가 가능하다.
  • 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
  • self-loop 뿐 아니라 loop/circuit 모두 가능하다.
  • 루트 노드라는 개념이 없다.
  • 부모-자식 관계라는 개념이 없다.
  • 순회는 DFS나 BFS로 이루어진다.
  • 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
  • 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
  • 간선의 유무는 그래프에 따라 다르다.
  • 해당 자료구조는 그래프 구조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다.
  • 이론적으로 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하지만, 실제 적용에 있어서 최적의 자료구조는 두 구조의 조합된 형태를 띤다.

• 종류

  • 무방향 그래프 & 방향 그래프
  • 가중치 그래프(Weighted Graph)
  • 연결 그래프 & 비연결 그래프
  • 사이클(Cycle) & 비순환 그래프(Acyclic Graph)
  • 완전 그래프(Complete Graph)

• 구현방법 2가지

  1. 인접 리스트(Adjacency List)

     • 모든 정점(vertex) 및 노드(Node)를 리스트(ArrayList, LinkedList)에 저장. 즉, 각각의 노드에 인접한 노드들을 저장
     • 정점 index를 통해 각 노드에 인접한 노드 리스트를 확인할 수 있다.
     • 무방향 그래프에서는 간선이 인접한 노드에 모두 저장되기 때문에 두번 저장된다.
       ex) 정점의 수: N, 간선의 수:E인 무방향 그래프인 경우
       N개의 리스트, N개의 배열, 2E개의 노드가 필요

  2. 인접 배열(Adjacency Matrix)

     • 정점 혹은 노드의 개수가 N인 그래프를 인접 행렬로 표현
     • 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요
     • 무방향 그래프를 인접 행렬로 표현한다면, 대칭 행렬이 된다.
     • 인접 리스트의 경우 인접한 노드의 리스트를 갖고 있기 때문에 인접한 노드를 쉽게 찾을 수 있지만, 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.

• 인접 리스트와 인접 행렬의 용도 차이

  1. 인접 리스트
     • 그래프 내에 적은 숫자의 간선만을 갖는 희소 그래프(Sparse Graph)인 경우
     • 어떤 노드에 인접한 노드를 찾는 경우
     • 단, 간선의 존재 여부와 정점의 차수: 정점 i의 리스트에 있는 도드의 수, 즉 정점 차수만큼의 시간이 필요
  2. 인접 행렬
     • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우
     • 두 정점을 연결하는 간선의 존재여부(M[i][j])를 O(1)안에 즉시 알 수 있다.
     • 정점의 차수는 O(N)안에 알 수 있다. (인접 배열의 i번 째 행 또는 열을 모두 더한다.)
     • 단, 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야한다.
     • 그래프에 존재하는 모든 간선의 수는 O(n^2) 안에 알 수 있다. (인접 행렬 전체를 검색)

코드 설계

1. 루트에서 시작한다.
2. 자식 노드들을 [1]에 저장한다.
3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5. 위의 과정을 반복한다.
6. 모든 노드를 방문하면 탐색을 마친다.

코드 구현

• 행렬로 구현한 그래프 (인접행렬)

public class Graph {
    private int[][] MATRIX; // 그래프 배열 선언

    public Graph() {}

    public Graph(int initSize) {
        this.MATRIX = new int[initSize + 1][initSize + 1];
    }

    public void put(int x, int y) {
        MATRIX[x][y] = MATRIX[y][x] = 1;
    }

    public void printGraph() {
        for (int i = 0; i < MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[i].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
    }
}

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

public class Graph {
    private int V;
    private LinkedList<Integer>[] adjacent;

    public Graph(int V) {
        this.V = V;
        this.adjacent = new LinkedList[V];
        for (int i = 0; i < V; i++)  adjacent[i] = new LinkedList<>();
    }

    public void addEdge(Graph graph, int src, int dest) {
        graph.adjacent[src].add(dest);
        graph.adjacent[dest].add(src);
    }

    public void printGraph(Graph graph) {
        for (int v = 0; v < graph.V; v++) {
            System.out.println("Adjacency list of vertex " + v);
            System.out.print("head");
            for (Integer pCrawl : graph.adjacent[v]) {
                System.out.print(" -> " + pCrawl);
            }
            System.out.println("\n");
        }
    }
}