그래프 이론 기초

이윤설·2024년 4월 2일

배워야 하는 이유

뭐든 배우기 이전에 배워야 하는 이유를 알아야한다.
그래프이론을 배워야 하는 이유는 너무나 간단하다!
정말 많은 곳에서 사용되고 있기 때문이다.

이러한 다양한 사회적, 기술적 문제를 해결하기 위해서 반드시 그래프 이론을 배워야 한다!

그래프의 종류

Directed Graph

말 그대로 방향이 존재하는 그래프를 뜻한다.
SNS 관계도를 통해 이해해보자.
Maria와 Tim은 서로 방향이 존재하기 때문에, 두 사람 간에 관계(친구, 연인, 가족 등일 수 있다)가 형성되어있음을 알 수 있다.

하지만 Joan은 Kanye를 대상으로 화살표가 있지만, Kanye는 Joan에게 화살표가 없다. 즉, Kanye는 Joan을 모르거나 친구로 등록하지 않았다는 뜻이다.

Node: 그래프의 요소
Edge: 노드들을 연결하는 선

Undirected Graph

이 그래프는 방향이 없다. 따라서 5개의 노드 간 서로 양방향의 관계가 있다는 것을 뜻한다. 서로 가족처럼 다 아는 사이라는 것이다.

Weighted Graph

가중치 그래프는 어떠한 노드에 갈 때마다 값이 가중되는 그래프다.
예를 들어, 한국에서 출발하여 일본에 경유했다가, 캐나다에 경유했다가, 알래스카에 도착할 때의 거리는 가중치 그래프 이론이 적용될 것이다.
각 노드 간의 거리가 1000km,2000km,500km라고 대충 가정하자.

가중치 그래프에서 각 노드 간의 거리를 표현할 때,
일반적으로 "노드 A는 가중치 W를 가진 노드 B와 연결되어 있다"라고 표현한다.

한국을 vertex-0, 일본을 vertex-1, 캐나다를 vertex-2, 알래스카를 vertex-3이라고 할 때:
vertex-0(한국)은 가중치 1000을 가진 vertex-1(일본)와 연결되어 있다.
vertex-1(일본)은 가중치 2000을 가진 vertex-2(캐나다)와 연결되어 있다.
vertex-2(캐나다)은 가중치 500을 가진 vertex-3(알래스카)와 연결되어 있다.

따라서, 이 가중치 그래프를 통해 한국에서 알래스카까지의 총 거리는 각 연결의 가중치를 합한 값, 즉 1000km + 2000km + 500km = 3500km로 표현할 수 있다.

주의) 가중 그래프는 방향/무방향 그래프와 완전히 독립적인 개념이 아니라, 방향성의 유무에 상관없이 적용할 수 있는 옵션의 개념이다.
즉, 가중치는 방향성이 있는 방향 그래프나 방향성이 없는 무방향 그래프 어느 쪽에도 추가할 수 있는 속성이다.

그래프를 구현하는 방법

인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)는 그래프를 컴퓨터 메모리에 표현하는 두 가지 주요 방법이다.
즉, 그래프 그림을 컴퓨터에 옮기기 위해 두가지 방법을 사용할 수 있다.
각각 장단점이 있기 때문에 빨리 살펴보자.

Adjacency Matrix

그래프 이론에서 인접 행렬은 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬이다.
예를 들어, 1번 노드에서 2번노드까지 연결이 있기 때문에 1을 작성하였고,
반대로 2번 노드로부터 1번 노드까지는 연결이 없기 때문에 0을 작성하면 된다.

공간 복잡도: O(V^2)

V는 정점(Vertex)의 수다.
정점의 수가 N개일 때, N x N 크기의 행렬을 사용하여 모든 가능한 간선의 존재 여부를 저장한다. 따라서 정점의 수에 비례하여 공간 복잡도가 제곱으로 증가한다.

시간 복잡도:
특정 간선의 존재 여부 확인: O(1)
특정 정점에 인접한 모든 정점 방문: O(V)

장단점

장점) 특정 노드 간의 연결을 빠르게 확인할 수 있다.
단점) 노드 수에 대해 제곱에 비례하는 메모리 공간을 필요로 한다.
따라서 노드 수가 많고 그래프가 희소한 경우에는 공간 효율성 측면에서 불리할 수 있다.

Adjacency List

방향 그래프로 나타내면, Edge들을 담는 Array에
노드 번호별로 index를 담아내고, 포인터를 통해 각각을 LinkedList로 연결한다.

각 인덱스는 'n번과 연결된 다른 노드들'을 담아둔다.
즉, 1번 노드에서 연결 리스트로 3번 노드까지 간다는 것을 저장한 뒤
2번 노드에서는 3번으로, 3번 노드에서는 4번으로 간다는 정보를 연결리스트로 붙인다.

그 결과, 2번 노드에 연결된 노드들을 찾으려면 전체 노드를 뒤져볼 필요 없이, 2번 노드에 연결된 노드들만 모두 꺼내오면 된다.

공간 복잡도: O(V + E)

V는 정점의 수, E는 간선(Edge)의 수다.
각 정점에 대해 그 정점에서 출발하는 간선들의 목록을 저장한다.
이 때, 모든 간선은 두 번 저장될 수 있으므로, 최악의 경우 공간 복잡도는 간선의 수에 비례한다. 희소 그래프에서는 인접 행렬에 비해 훨씬 효율적인 공간 사용이 가능하다.

시간 복잡도:
특정 간선의 존재 여부 확인: O(V)
특정 정점에 인접한 모든 정점 방문: O(deg(V))
dev(V)는 정점 V의 차수(degree)를 의미하며, 이는 V에서 출발하거나 V로 들어오는 간선의 총 수를 의미한다.

정리

인접 행렬(Adjacency Matrix)
- 장점:
  - 두 노드 사이의 연결 여부를 상수 시간에 확인할 수 있다.
  - 희소 그래프(Sparse Graph, 간선의 수가 적은 그래프)가 아닐 경우, 공간 효율적이다.
- 단점:
  - 희소 그래프일 경우, 메모리 낭비가 발생한다.
  - 노드의 개수가 많아지면 공간 복잡도가 높아진다.
인접 리스트(Adjacency List)
- 장점:
  - 희소 그래프에 적합하다.
  - 노드와 간선 추가/삭제가 용이하다.
  - 메모리 사용량이 적다.
- 단점:
  - 두 노드 사이의 연결 여부를 확인하는 데 시간이 더 걸린다.
  - 인접 리스트 자체를 표현하는 데 추가적인 메모리가 필요한다.

다음과 같은 경우에는 인접 행렬을 사용하는 것이 좋다:

그래프가 밀집 그래프(Dense Graph, 간선의 수가 많은 그래프)인 경우
두 노드 사이의 연결 여부를 자주 확인해야 하는 경우
노드의 수가 적은 경우

다음과 같은 경우에 인접 리스트를 사용하는 것이 좋다:

그래프가 희소 그래프인 경우
노드와 간선의 추가/삭제가 자주 발생하는 경우
메모리 사용량이 제한적인 경우

희소 그래프

희소 그래프(Sparse Graph)
- 그래프에서 간선의 수가 노드의 수에 비해 상대적으로 적은 그래프다.
- 간선의 밀도(Density)가 낮다.
- 예를 들어, 100개의 노드가 있고 200개의 간선이 있다면 희소 그래프라고 볼 수 있다.
노드/간선의 개수가 적은 그래프
- 단순히 그래프에 포함된 노드와 간선의 절대적인 개수가 적은 그래프를 의미한다.
- 노드와 간선의 개수 자체가 작은 그래프다.
- 예를 들어, 10개의 노드와 20개의 간선이 있는 그래프는 절대적인 크기가 작지만, 밀도가 높다면 희소 그래프라고 볼 수 없다.

희소 그래프는 상대적인 개념이며, 노드와 간선의 개수가 적은 것과는 별개의 개념이다. 노드와 간선의 개수가 작더라도 밀도가 높다면 희소 그래프가 아닐 수 있다.

일반적으로 밀도가 낮은 희소 그래프에서는 인접 리스트 표현이 더 효율적이며, 밀도가 높은 그래프에서는 인접 행렬 표현이 더 효율적이다.

DFS와 BFS

public class DFS와_BFS {

    static StringBuilder sb = new StringBuilder();
    static boolean[] check;
    static int[][] arr;
    static int node, line, start;
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        arr = new int[node + 1][node + 1];
        check = new boolean[node + 1];

        for (int i = 0; i < line; i++) {
            StringTokenizer str = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());

            arr[a][b] = arr[b][a] = 1;
        }

        dfs(start);
        sb.append("\n");
        check = new boolean[node + 1];

        bfs(start);

        System.out.println(sb);

    }

    public static void dfs(int start) {

        check[start] = true;
        sb.append(start + " ");

        for (int i = 1; i <= node; i++) {
            if (arr[start][i] == 1 && !check[i])
                dfs(i);
        }

    }

    public static void bfs(int start) {
        queue.add(start);
        check[start] = true;

        while (!queue.isEmpty()) {

            start = queue.poll();
            sb.append(start + " ");

            for (int i = 1; i <= node; i++) {
                if (arr[start][i] == 1 && !check[i]) {
                    queue.add(i);
                    check[i] = true;
                }
            }
        }
    }
}