🐹 6. Graphs

04. 트리와 그래프

[ 그래프 ]

: 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은것

→ 트리는 그래프의 한 종류이다. 사이클이 없는 하나의 연결 그래프이다.

• 그래프는 방향성이 있는 그래프와 없는 그래프가 있다.
• 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있는데, 모든 정점 쌍 간에 경로가 존재하는 그래프는 ‘연결 그래프’라고 부른다.
• 그래프에는 사이클이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프는 ‘비순환 그래프’라고 부른다.

인접 리스트(adjacency list)

모든 정점(혹은 노드)를 인접 리스트에 저장한다.

→ 무방향 그래프에서는 (a, b)간선은 두 번 저장한다. 한 번은 a 정점에 인접한 간선을 저장하고 다른 한 번은 b에 인접한 간선을 저장한다.

class Graph {
    public Node[] nodes;
}

class Node {
    public String name;
    public Node[] children;
}

• 트리 : 특정 노드 하나(루트 노드)에서 다른 모든 노드로 접근이 가능
• 그래프 : 트리와 달리 특정 노드에서 다른 모든 노드로 접근이 불가능 → Graph라는 클래스를 사용한다.

그래프를 위한 추가적인 클래스를 따로 구현할 필요 없다. 배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열, 동적 가변 크기 배열(arraylist), 연결리스트(linked list) 등)를 이용해 인접 리스트를 표현할 수 있다.

0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5

인접 행렬(adjacency matrix)

: N*N boolean 행렬로 matrix[i][j]가 true라면 i에서 j로의 간선이 있다는 뜻이다.

무방향 그래프는 인접 행렬로 표현한다면 이 행렬은 대칭행렬(symmetric matrix)이 된다.

인접 리스트를 사용한 그래프 알고리즘(ex. bfs)을 인접 행렬로도 사용 가능하다. 하지만 인접 행렬은 효율성이 떨어진다.

→ 인접 리스트에서는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만, 인접 행렬에서는 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 알 수 있다.

그래프 탐색

일반적으로 깊이 우선 탐색(depth-first search)과 너비 우선 탐색(breadth-first search)이 있다.

• 깊이 우선 탐색(DFS)

  : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

  → 모든 노드를 방문하고자 할 때

• 너비 우선 탐색(BFS)

  : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

  → 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 떄

깊이 우선 탐색(DFS)

DFS는 a 노드를 방문한 뒤 a와 인접한 노드들을 차례로 순회한다. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 이전에 b의 이웃 노드들을 전부 방문해야 한다.

→ b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다.

• DFS 종류 : 전위 순회를 포함한 다른 형태의 트리 순회

void search(Node root) {
    if (root == null) return;
    visit(root);
    root.visited = true;
    foreach (Node n in root.adjacent) {
        if (n.visited == false) {
            search(n);
        }
    }
}

너비 우선 탐색(BFS)

BFS는 재귀적으로 동작하지 않고 큐(queue)를 사용한다.

a 노드에서 시작한다고 했을 때, BFS는 a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

→ a에서 시작해서 거리에 따라 단계별로 탐색한다.

void search(Node root) {
    Queue queue = new Queue();
    root.marked = true;
    queue.enqueue(root); // 큐의 끝에 추가

    while (!queue.isEmpty()) {
        Node r = queue.dequeue(); // 큐의 앞에서 뽑아냄
        visit(r);
        foreach (Node n in r.adjacent) {
            if (n.marked == false) {
                n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}

양방향 탐색(bidirectional search)

→ 출발지와 도착지 사이에 최단 경로를 찾을 때 사용

출발지와 도착지 두 노드에서 동시에 너비 우선 탐색을 수행한 뒤, 두 탐색 지점이 충돌하는 경우에 경로를 찾는다.

양방향 탐색 방식이 왜 더 빠를까?

모든 노드가 적어도 k개와 이웃 노드와 연결되어 있고 s에서 t로의 최단 거리가 d가 되는 그래프를 생각해보자.

• 너비 우선 탐색

  전통적인 너비 우선 탐색을 사용하면 첫 단계에서 k개의 노드를 탐색해야 한다. 다음 단계에선 k개의 노드들 또한 이웃한 k개의 노드를 탐색해야 하므로 총 $k^2$개의 노드를 탐색해야 한다.

  → 이를 d번 반복하면 총 $O(k^d)$개의 노드를 탐색해야 한다.

• 양방향 탐색

  두 탐색 알고리즘이 대략 d/2단계(s와 t 사이의 중간 지점)까지 탐색한 후에 충돌할 것이다. 따라서 s와 t 각각에서 방문하게 될 노드의 수는 대략 $k^{d/2}$개가 될 것이다.

  → 방문하게 될 전체 노드는 대략 $2*k^{d/2}$, $O(k^{d/2})$개가 된다.