그래프(Graph) 자료구조와 탐색

그래프(Graph)

비선형 자료구조
원소들 간 n:m의 관계를 가지는 자료구조
사물 혹은 사람, 추상적 개념 등의 관계성을 표현한 자료구조
정점(vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조
차수(Degree) : 정점에 연결된 간선의 수

그래프의 유형

무향 그래프(Undirected Graph) : 간선에 방향이 없어 정점 간 연결관계만 나타낸 그래프
유향 그래프(Directed Graph) : 간선에 방향이 있어 출발 정점과 도착 정점을 나타낸 그래프
가중치 그래프(Weighted Graph) : 간선에 가중치가 부여되어 특정 정점 간 거리, 이동 비용, 기타 가중치 등의 값을 표현한 그래프
사이클 없는 방향 그래프(DAG, Directed Acyclic Graph) : 한 정점에서 다른 정점들을 돌아 다시 자신에게 돌아오는 순환적인 사이클이 존재하지 않는, 일방향성 그래프
트리도 그래프의 일종
- 부모 노드와 자식 노드 사이에는 유일한 경로가 존재함

인접 정점과 그래프 경로

인접(Adjacency) : 두 정점 사이에 간선이 존재할 경우 두 정점은 연결되어 있고 인접한 것임
경로(Path) : 한 정점에서 시작하여 다른 정점까지 도달하기까지의 간선 정보
- 단순 경로 : 시작 정점과 끝 정점을 제외하고 중복된 정점이 없음
- 사이클(Cyclic) : 경로의 시작 정점과 끝 정점이 같음

그래프의 표현

인접 행렬(Adjacent Matrix)

V * V 크기의 2차원 배열을 이용하여 두 정점 사이 간선의 유무를 저장
행과 열의 인덱스는 두 정점을 표현함
무향 그래프의 경우 2차원 배열 위에 기울기가 -1인 가상의 직선이 존재한다고 생각하고 이 직선을 기준으로 서로 대칭하는 형태로 값이 들어가 있음
가중치가 없는 그래프의 경우 boolean형 배열을 생성하여, 간선이 존재하면 true, 간선이 없으면 false를 저장할 수 있음
가중치가 있는 그래프의 경우 배열의 값에 가중치 값을 저장할 수 있음
인접 행렬을 이용하여 그래프를 표현할 경우 희소 그래프(Sparse Graph) 표현 시 메모리 낭비가 발생할 수 있음
- 희소 그래프란 그래프의 정점 사이 간선이 비교적 적은 그래프를 의미 (<-> 밀집 그래프(Dense Graph))
정점 중심 문제를 해결할 때 적합

Java

public void adjacentMatrix() {
    int[][] vertexs = {{1, 2}, {1, 4}, {3, 2}, {4, 5}, {5, 3}};    // 인접 정점 정보
    int N;                                         // 정점의 개수
    boolean[][] adjMatrix = new boolean[N][N];     // 가중치가 없는 인접 행렬

    for (int i=0; i<vertexs.length; i++) {
        int from = vertexs[i][0];
        int to = vertexs[i][1];

        adjMatrix[from][to] = true;
        adjMatrix[to][from] = true;
    }
}

인접 리스트(Adjacent List)

하나의 정점에 대한 인접 정점들을 연결 리스트에 노드 형태로 저장
리스트의 인덱스는 그래프의 모든 정점을 표현함
무향 그래프의 경우 인접한 정점 a와 b를 표현할 때 정점 a를 리스트의 인덱스에 대치시키고 정점 b는 노드 형태로 리스트의 a 인덱스에 저장함. 반대로 정점 b 역시 리스트의 인덱스에 대치시키고 정점 a는 노드 형태로 리스트의 b 인덱스에 저장해야 함.
- 무향 그래프의 노드 수 = 간선의 수 * 2
유향 그래프는 진출 정점만 리스트의 인덱스에 대치시키고 진입 정점만 노드 형태로 저장하면 됨
- 유향 그래프의 노드 수 = 간선의 수
구현이 조금 까다롭지만 간선이 비교적 적은 희소 그래프를 표현하기에 인접 행렬보다 효율적임
정점 중심 문제를 해결할 때 적합

Java

class adjacentList() {

    static class Node {
        int vertex;    // 인접 정점 인덱스
        Node link;     // 인접 정점 링크

        public Node(int vertex, Node link) {
            super();
            this.vertex = vertex;
            this.link = link;
        }
    }

    public void adjacentList() {
        int[][] vertexs = {{1, 2}, {1, 4}, {3, 2}, {4, 5}, {5, 3}};    // 인접 정점 정보
        int N;                                         // 정점의 개수
        Node[] adjList = new Node[N];     // 가중치가 없는 인접 행렬

        for (int i=0; i<vertexs.length; i++) {
            int from = vertexs[i][0];
            int to = vertexs[i][1];

            adjList[from] = new Node(to, adjMatrix[from]);
            adjList[to] = new Node(from, adjMatrix[to]);
        }
    }
}

간선 리스트(Edge List)

두 정점에 대한 간선 자체를 객체로 표현하여 리스트로 저장
간선을 표현하는 두 정점(시작 정점, 끝 정점)의 정보를 표현

그래프 탐색

비선형 자료구조인 그래프의 모든 정점을 빠짐없이 탐색하는 기법

트리 자료구조와 동일하게 너비 우선 탐색과 깊이 우선 탐색 기법이 존재함. 트리의 경우 자식 노드에게 연결된 부모 노드는 단 한개만 존재하므로 한 노드에 도착할 수 있는 출발점은 해당 노드의 부모노드 하나뿐임. 하지만, 그래프의 경우 한 정점에 인접한 정점이 여러개일 수 있으므로 해당 정점으로 도착할 수 있는 출발점이 여러개임.

따라서 그래프에서의 탐색에서는 정점에 대한 방문 체크를 필수적으로 해주어야지 같은 정점을 중복해서 방문하지 않음!!

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

탐색 시작 정점부터 모든 인접한 정점들을 차례대로 방문한 뒤, 방문했던 정점을 시작점으로 하여 다시 해당 정점의 인접한 정점들을 모두 방문하는 방식
인접한 정점에 대한 탐색이 끝나야 해당 정점들의 인접한 노드를 방문할 수 있으므로 선입 선출 형태의 자료구조인 큐(Queue)를 사용하여 구현할 수 있음

Java

// 인접 행렬 그래프 bfs

public void adjMatrixBfs() {
    Queue<Integer> q = new LinkedList<>();      // 시작 정점 저장
    boolean[] visited = new boolean[N];         // 정점 방문 여부 기억
   
    q.offer(0);           // 시작 정점의 인덱스
    visited[0] = true;    // 시작 정점 방문 체크

    while(!q.isEmpty()) {
        int current = q.poll();
        
        System.out.println(current + " ");

        for (int i=0; i<N; i++) {     // 그래프의 모든 정점에 대해
            if (!visited[i] && adjMatrix[current][i]) {     // 아직 방문 안했고 현재 정점에 인접한 정점이면
                q.offer(i);           // 탐색을 위해 큐 맨 뒷단에 삽입하고
                visited[i] = true;    // 미리 방문 처리함으로써 큐에 정점이 중복적으로 삽입되는 것을 막음
            }
        }
    }
}

Java

// 인접 리스트 그래프 bfs

public void adjListBfs() {
    Queue<Integer> q = new LinkedList<>();      // 시작 정점 저장
    boolean[] visited = new boolean[N];         // 정점 방문 여부 기억
   
    q.offer(0);           // 시작 정점의 인덱스
    visited[0] = true;    // 시작 정점 방문 체크

    while(!q.isEmpty()) {
        int current = q.poll();
        
        System.out.println(current + " ");

        for (Node i=adjList[current]; i!=null; i=i.link) {     // 현재 정점의 인접 리스트에 저장된 인접한 정점들에 대해서만
            if (!visited[i.vertex]) {     // 아직 방문 안했으면
                q.offer(i.vertex);           // 탐색을 위해 큐 맨 뒷단에 삽입하고
                visited[i.vertex] = true;    // 미리 방문 처리함으로써 큐에 정점이 중복적으로 삽입되는 것을 막음
            }
        }
    }
}

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

시작 정점의 한 방향으로 갈 수 있는 경로가 존재할 때까지 계속해서 깊게 탐색. 더 이상 방문할 수 있는 경로가 없으면 마지막으로 만났던 갈림길이 있던 정점으로 돌아와 다른 방향의 정점을 같은 방식으로 계속해서 깊게 탐색하는 방식
인접한 정점의 인접한 정점을 먼저 깊게 방문했다가 방문할 노드가 없을 경우 돌아와서 다른 인접 정점으로 깊게 들어가야 하므로 재귀적으로 구현하거나, 후입 선출 형태의 자료구조인 스택(Stack)을 사용하여 구현할 수 있음

Java

// 인접 행렬 그래프 bfs

public void dfs(int current, boolean[] visited) {
    visited[current] = true;       // 현재 탐색 정점 방문 처리

    System.out.println(current + " ");

    for (int i=0; i<N; i++) {     // 그래프의 모든 정점에 대해
        // 아직 방문 안했고 현재 정점에 인접한 정점이면 해당 정점을 다시 시작점으로 삼아 인접한 정점을 깊게 탐색
        if (!visited[i] && adjMatrix[current][i]) dfs(i, visited);
    }
}

Java

// 인접 리스트 그래프 dfs

public void dfs(int current, boolean[] visited) {
    visited[current] = true;       // 현재 탐색 정점 방문 처리

    System.out.println(current + " ");

    for (Node i=adjList[current]; i!=null; i=i.link) {      // 현재 정점의 인접 리스트에 저장된 인접한 정점들에 대해서만
        // 아직 방문 안했으면 해당 정점을 다시 시작점으로 삼아 인접한 정점을 깊게 탐색
        if (!visited[i.vertex]) dfs(i.vertex, visited);
    }
}

그래프(Graph) 자료구조와 탐색