18장 그래프로 뭐든지 연결하기

• 친구를 맺어주는 소셜 네트워크를 만든다고 하자. 친구 관계는 상호적이다.
• 이런 데이터를 가장 잘 조직하는 방법은 무엇일까?
• 한 가지, 매우 간단한 접근 방식은 2차원 배열로 친구 관계 리스트를 저장하는 것이다.
• 그러나 2차원 배열로는 A의 친구가 누구인지 빠르게 알 수 없다. 컴퓨터는 목록을 전부 확인해야 하므로 O(N)이 필요하다.
• 그래프를 사용하면 A의 친구를 O(1)만에 빠르게 찾을 수 있다.

1. 그래프

• 그래프는 관계에 특화된 자료구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다.

1.1 그래프 대 트리

• 그래프는 앞서 다뤘던 트리와 비슷하다. 사실 트리도 그래프의 한 종류다.
• 모든 트리는 그래프이지만, 모든 그래프가 트리는 아니다.
• 트리로 규정되는 그래프는 사이클이 없어야 하며, 모든 노드가 서로 연결되어야 한다.
  • 그래프에는 사이클을 형성하는 노드, 즉 순환적으로 참조하는 노드가 있을 수 있다.
  • 트리의 모든 노드는 어떻게든, 간접적으로라도 다른 노드와 연결되어야 한다.
  • 하지만 그래프는 완전히 연결되지 않을 수 있다.
  • 즉, 관계가 아무와도 없는 노드가 존재할 수 있다.

1.2 그래프 용어

• 그래프에서는 각 노드를 정점Vertex라고 부른다.
• 정점을 잇는 선도 간선Edge라고 부른다.
• 간선으로 연결된 정점은 서로 인접한다Adjacent고 말한다.
• 인접한 정점은 이웃Neighbor라고 부른다.
• 모든 정점이 어떻게든 서로 연결된 그래프를 연결 그래프Connected Graph라고 부른다.

2. 방향 그래프

• 어떤 소셜 네트워크에서는 관계가 상호적이지 않다.
• 예를 들어 A가 B를 팔로우할 수 있지만, B가 반드시 A를 팔로우하지 않을 수 있다.
• 이와 같은 관계를 나타내는 그래프를 방향 그래프Directed Graph라고 부른다.

3. 객체 지향 그래프 구현

• 연결 그래프를 사용하면 Vertex 클래스 하나로 앞으로 나올 모든 알고리즘을 다룰 수 있다.
• 모든 정점이 연결되어 있으므로 정점 하나에만 접근할 수 있으면 거기서부터 다른 정점을 모두 찾을 수 있다.
• 하지만 연결되지 않은 그래프를 다룰 때는 한 정점에서 시작해 모든 정점을 찾는 것이 불가능할 수 있다. 이럴 때는 그래프 정점을 배열과 같은 추가 데이터 구조에 저장한 후 접근해야 할 수도 있다.

4. 그래프 탐색

• 정점 찾기는 가장 흔한 그래프 연산 중 하나다.
• 그래프에서 탐색은 그래프 내 한 정점에 접근할 수 있을 때 그 정점과 어떻게든 연결된 또 다른 특정 정점을 찾는 것이다.
• 경로Path는 그래프 용어로 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻한다.
• 특정 정점을 찾는 경우가 아니어도 탐색을 사용할 수 있다. 즉 그래프 탐색으로 그래프 순회만 할 수도 있다.
• 그래프의 모든 정점에 어떤 연산을 수행하고 싶을 때 유용하다.

5. 깊이 우선 탐색

• 그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색, 두 방식이 널리 쓰인다.
• 둘 다 문제 없이 그래프를 탐색하지만 고유한 이점을 제공한다.
• DFS, 깊이 우선 탐색은 이진 트리 순회 알고리즘과 상당히 유사하다.
• 어떤 그래프 탐색 알고리즘이든 핵심은, 지금까지 어떤 정점을 방문했는지 기록하는 것이다.
• 그래프에는 사이클이 있을 수 있으므로 방문을 기록하지 않는다면 무한 사이클에 빠질 수 있다.
• 방문을 기록할 수 있는 한 가지 방법은 해시 테이블을 사용하는 것이다. 각 정점을 방문할 때마다 그 정점을 키로 해시 테이블에 추가하고 true와 같은 임의의 값을 할당한다. 해당 정점을 방문했다면 해시 테이블에 그 값이 존재할 것이다.
• DFS의 동작 방식은 다음과 같다.
  1. 그래프 내 임의의 정점에서 시작한다.
  2. 현재 정점을 해시 테이블에 추가하여 방문했음을 기록한다.
  3. 현재 정점의 인접 정점을 순회한다.
  4. 3-1. 방문 했던 인접 정점이면 무시한다.
  5. 방문하지 않았던 인접 정점이면 그 정점에 대해 재귀적으로 DFS를 수행한다.

6. 너비 우선 탐색

• 흔히 BFS로 줄여 부르는 너비 우선 탐색은 그래프를 탐색하는 또 다른 방법이다.
• BFS는 재귀를 사용하지 않는다. 대신 앞서 배웠던 큐를 사용한다.
  • 큐는 FIFO 자료구조로서 먼저 들어간 데이터를 먼저 처리한다.
• BFS의 동작 방식은 다음과 같다.
  1. 그래프 내 아무 정점에서나 시작한다. 이 정점을 “시작 정점”이라고 부른다.
  2. 시작 정점을 해시 테이블에 추가해 방문했다고 표시한다.
  3. 시작 정점을 큐에 추가한다.
  4. 큐가 빌 때까지 실행하는 루프를 시작한다.
  5. 루프 안에서 큐의 첫 번째 정점을 삭제한다. 이 정점을 “현재 정점”이라고 부른다.
  6. 현재 정점의 인접 정점을 순회한다.
  7. 이미 방문한 인접 정점이면 무시한다.
  8. 아직 방문하지 않은 인접 정점이면 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.
  9. 큐가 빌 때까지 루프(4단계부터)를 반복한다.

6.3 깊이 우선 탐색 VS 너비 우선 탐색

• 너비 우선 탐색은 시작 정점과 가장 가까운 정점을 모두 순회한 후 멀어진다.
• 깊이 우선 탐색은 즉시 시작 정점에서 최대한 멀어진다.
• 그러니 항상 이렇게 물어야 한다: 그래프를 탐색하는 동안 시작 정점 가까이 있고 싶은가, 아니면 무조건 멀리 떨어지고 싶은가?
  • 가까이 있고 싶다면 너비 우선 탐색을, 빨리 멀어져야 한다면 깊이 우선 탐색을 사용하면 된다.

7. 그래프 탐색의 효율성

• 빅 오 표기법으로 그래프 탐색의 시간 복잡도를 분석해 보자.
• DFS와 BF 모두 그래프 내 정점을 모두 순회한다. 언뜻 정점이 N개일 때 O(N)처럼 보인다.
• 그러나 두 탐색 알고리즘은 순회하는 각 정점의 인접 정점까지 모두 순회한다.
• 이미 방문했던 정점이면 무시할 수 있으나 어차피 방문 여부를 확인하는 단계가 필요하다.
• 즉 방문하는 각 정점의 인접 이웃까지 확인하는 단계를 포함한다.
• 정점마다 인접 정점의 개수가 다르니 빅 오 표기법으로 딱 고정해서 말하기 어렵다.
• 즉 그래프 내 정점 개수만으로는 단계를 계산할 수 없다. 각 정점의 인접 정점이 몇 개인지도 함께 고려해야 한다.
• 그러므로 그래프 탐색의 효율성을 실질적으로 묘사하려면 변수 두 개가 필요하다.
• 그래프 내 정점 수와 각 정점들의 총 인접 정점 수이다.

7.1 O(V+E)

• V는 그래프 내 정점 수다.
• E는 간선을 뜻하며 그래프 내 간선 수를 나타낸다.
• 한 가지 분명한 것은 간선 수가 늘어나면 단계 수도 늘어난다는 사실이다.
• 결론적으로 그래프 탐색은 DFS와 BFS 둘 다 최악의 시나리오에서 O(V+E)이다.

8. 가중 그래프

• 그래프에는 다양한 변형이 존재한다.
• 그래프 간선에 정보를 추가하는 가중 그래프Weighted graph 역시 또 하나의 유용한 그래프 유형이다.

8.2 최단 경로 문제

• 가중 그래프는 갖가지 데이터 세트를 훌륭하게 모델링하며 그 데이터를 최대한 활용하는 강력한 알고리즘까지 지원한다.
• 목적지를 찾는 최소 비용을 찾는 문제를 최단 경로 문제라고 부른다.
• 형태는 여러 가지다. 그래프에서 가장 짧은 경로를 찾고 싶을 수도 있고, 그래프에서 가장 비용이 저렴한 경로를 찾고 싶을 수도 있따.

9. 데이크스트라의 알고리즘

• 최단 경로 문제를 푸는 알고리즘 중 굉장히 흥미로운 알고리즘이 있다.
• 바로 데이크스트라의 알고리즘이다.

9.2 데이크스트라의 알고리즘 준비

• 이 알고리즘을 수행하면 시작 정점에서 모든 정점으로 가는 가장 저렴한 비용을 알게 된다.
• 알고리즘의 수행에 앞서, 두 가지 데이터가 필요하다.
• cheapest_price_table: 이 데이터는 시작 정점으로부터 다른 정점까지의 최소 비용을 저장한다.
• cheapest_previous_stopover_vertex_table: 이 데이터는 각 정점에 갈 때 “시작 정점”에서 가장 저렴한 비용으로 가기 위해 마지막으로 경유하는 정점을 저장한다.

9.3 데이크스트라의 알고리즘 단계

1. 시작 정점에 방문하여 “현재 정점”으로 만든다.
2. 현재 정점에서 각 인접 정점으로의 비용을 확인한다.
3. 시작 정점에서 인접 정점으로의 비용이 현재 저장된 cheapest_price_table의 비용보다 저렴하면, 혹은 인접 정점이 아직 cheapest_price_table에 없으면 다음의 작업을 수행한다.
   1. cheapest_price_table을 더 저렴한 비용으로 업데이트한다.
   2. 인접 정점을 키로, 현재 정점을 값으로 cheapest_previous_stopover_vertex_table을 업데이트한다.
4. 다음으로 방문하지 않은 정점 중 가장 저렴한 비용의 정점에 방문하여 현재 정점으로 만든다.
5. 모든 정점에 방문할 때까지 2~4단계를 반복한다.

9.6 데이크스트라의 알고리즘의 효율성

• 이 알고리즘은 가중 그래프에서 최단 경로를 찾는 방법을 일반적으로 설명할 뿐 정밀한 코드 구현을 열거하지는 않는다. 실제로 이 알고리즘을 작성하는 여러 변형이 존재한다.
• 결국 정밀한 구현이 알고리즘의 시간 복잡도에 상당한 영향을 끼친다.
• 방문하지 않은 도시를 배열에 저장하면 O(V^2)이다.
• 배열 대신 우선순위 큐로 구현하면 속도가 더 빠르다.
• 하지만 어떤 구현을 선택해도 다른 대안보다 이득이며 그래프에 존재하는 가능한 경로를 모두 찾아 가장 빠른 경로를 선택하게 해 준다.
• 데이크스트라의 알고리즘은 그래프를 신중히 탐색하고 최단 경로에 집중하게 해 주는 확실한 방법이다.

10. 마무리

• 그래프는 관계를 포함하는 데이터를 처리할 때 매우 강력한 도구이며, 코드 속도를 높임과 동시에 까다로운 문제를 푸는 데 도움이 될 수 있다.
• 사실 그래프라는 자료 구조에는 흥미롭고 유용한 알고리즘이 정말 많다.
  • 최소 스패닝 트리, 위상 정렬, 양방향 탐색, 플로이드-워셜 알고리즘, 벨먼-포드 알고리즘, 그래프 채색 등이다.
• 지금까지 줄곧 주된 관심사는 코드를 얼마나 빨리 실행시키는가였다. 즉, 시간 관점에서 코드가 얼마나 효율적으로 실행되는지 측정했고, 알고리즘에 걸리는 단계 수가 효율성의 측정 기준이었다.
• 그러나 속도 외에 다른 방식으로도 효율성을 측정할 수 있다.
• 특히 자료구조나 알고리즘이 얼마나 많은 메모리를 소비하느냐가 중요할 수도 있다.
• 다음 장에서는 공간 관점에서 코드의 효율성을 분석하는 법을 배운다.