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

페이스북과 같은 소셜 네트워크에서 친구 관계는 상호적이다.

이를 구현하기 위해 2차원 배열을 사용한다면 특정 유저의 친구를 찾기 위해 목록 내 관계를 일일이 확인해야 하고, 이는 O(N)이 걸리는 느린 방법이다.

이때 그래프 자료 구조를 사용하면 O(1) 시간만에 찾을 수 있다.

18.1 그래프

그래프는 관계에 특화된 자료구조다.

소셜 네트워크의 예시에선 한 사람은 한 노드로, 사람 관 친구 관계는 선으로 표현한다.

18.1.1 그래프 대 트리

트리도 그래프의 한 종류다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다.

모든 트리는 그래프지만, 그래프가 모두 트리는 아니다.
트리로 규정되는 그래프는 사이클이 있을 수 없으며, 모든 노드가 서로 연결되어야 한다.

그래프에는 사이클을 형성하는 노드, 즉 순환적으로 참조하는 노드가 있을 수 있다.
그래프는 완전히 연결되지 않은 노드가 있을 수 있다.
소셜 네트워크에 방금 가입해 친구가 0명인 회원이 있다면 노드는 존재하지만 연결된 친구가 한 명도 없는 상태이다.

18.1.2 그래프 용어

그래프에서는 각 노드를 정점 vertex이라고 부른다.
정점을 잇는 선을 그래프 용어로 간선 edge 이라고 부른다.
간선으로 연결된 정점은 서로 인접한다 adjacent고 말하며, 인접한 정점을 이웃 neighbor이라고도 부른다.

모든 정점이 어떻게든 서로 연결된 그래프를 따로 연결 그래프 connected graph라고 부른다.

18.1.3 기초 그래프구현

객체 지향 클래스로 그래프를 표현해 코드를 구성하지만 기초 해시 테이블로도 가장 기본적인 그래프를 표현할 수 있다.

해시 테이블로 구현하면 다음과 같다.

const friends = new Map([
  ["Alice", ["Bob", "Diana", "Fred"]],
  ["Bob", ["Alice", "Cynthia", "Diana"]],
  ["Cynthia", ["Bob"]],
  ["Diana", ["Alice", "Bob", "Fred"]],
  ["Elise", ["Fred"]],
  ["Fred", ["Alice", "Diana", "Elise"]],
]);

friends.get("Alice");		// [ 'Bob', 'Diana', 'Fred' ]

해시 테이블의 모든 키 값은 한 단계로 찾을 수 있으므로 앨리스의 친구를 O(1)에 찾을 수 있다.

18.2 방향 그래프

트위터와 같은 소셜 네트워크에서는 관계가 상호적이지 않다.
앨리스는 밥을 팔로우할 수 있지만, 밥이 반드시 앨리스를 팔로우하진 않는다.

이것을 그래프로 나타내면 방향 그래프라 부른다. 간선은 화살표로 표시하며, 화살표는 관계의 방향을 나타낸다.

const folowees = new Map([
  ["Alice", ["Bob", "Cynthia"]],
  ["Bob", ["Cynthia"]],
  ["Cynthia", ["Bob"]],
]);

해시 테이블로 구현할 수 있으며, 배열을 사용해 각각 누구를 팔로우하는지 나타낸다는 점만 다르다.

18.3 객체 지향 그래프 구현

객체 지향 그래프를 구현할 때는 다음과 같이 시작한다.

class Vertex {
  constructor(value) {
    this.value = value;
    this.adjacentVertices = [];
  }

  addAdjacentVertex(vertex) {
    this.adjacentVertices.push(vertex);
  }
}

소셜 네트워크에서 Vertex 클래스를 통해 만들어진 인스턴스는 한 사람을 나타내고, value 속성은 그 사람의 이름을 포함하는 문자열, adjacentVertices 배열은 그 사람과 연결되는 모든 정점을 포함한다.

addAdjacentVertex 메서드를 이용해 주어진 정점에 인접한 정점을 추가할 수 있다.

이 클래스를 통해 방향 그래프를 만들 수 있다.

const alice = new Vertex("alice");
const bob = new Vertex("bob");
const cynthia = new Vertex("cynthia");

alice.addAdjacentVertex(bob);
alice.addAdjacentVertex(cynthia);
bob.addAdjacentVertex(cynthia);
cynthia.addAdjacentVertex(bob);

모든 친구 관계가 상호적인 소셜 네트워크를 위한 무방향 그래프를 만든다면, 밥을 앨리스의 친구 목록에 추가할 때 자동으로 앨리스도 밥의 친구 목록에 추가하는 것이 타당하다.

addAdjacentVertex(vertex) {
  if (this.adjacentVertices.includes(vertex)) {
    return;
  }
  this.adjacentVertices.push(vertex);
  vertex.addAdjacentVertex(this);
}

addAdjacentVertex 메서드를 수정한다.
객체의 adjacentVertices 배열에 다른 정점을 추가한뒤, 그 정점의 addAdjacentVertex 메서드로 객체를 추가한다.

여기서 끝내면 서로가 끝없이 addAdjacentVertex 메서드를 호출하므로 무한 루프가 발생한다. 따라서 친구 목록을 먼저 검사하고, 추가하려는 친구가 이미 목록에 있으면 메서드를 중지하도록 한다.

이후 설명은 연결된 그래프만 다룬다. 연결 그래프를 사용하면 이미 작성한 Vertex 클래스로 앞으로 나올 알고리즘을 모두 다룰 수 있다.

연결되지 않은 그래프를 다룰 때는 한 정점에서 시작해 모든 정점을 찾는 것이 불가능할 수 있으므로, 그래프 정점을 배열과 같은 추가 데이터 구조에 저장한 후 접근해야 할 수도 있다.

18.4 그래프 탐색

정점 찾기는 가장 흔한 그래프 연산 중 하나다.

그래프 용어 "탐색"은 몇 가지 의미를 함축한다. 가장 단순한 의미에선 그래프 어딘가에 있는 특정 정점을 찾는 것이다. 보다 특정한 의미로는 그래프 내 한 정점에 접근할 수 있을 때 그 정점과 어떻게든 연결된 또 다른 특정 정점을 찾는 것이다.

이는 그래프 내의 한 정점에서, 다른 특정 정점까지의 경로를 찾는다는 뜻이다.
경로는 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻한다.

• 연결 그래프에서 특정 정점을 찾는 경우
  • 임의의 정점 하나만 접근할 수 있으면 탐색으로 전체 그래프 내 어떤 정점이든 찾을 수 있다.
• 두 정점이 연결되어 있는지 알아내는 경우
• 그래프의 모든 정점에 어떤 연산을 수행하고 싶은 경우

등에 효과적으로 사용할 수 있다.

18.5 깊이 우선 탐색

그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색 두 방식이 널리 쓰인다.

깊이 우선 탐색 Depth-First-Search, DFS은 이진 트리 순회 알고리즘과 상당히 유사하다.

어떤 그래프 탐색 알고리즘이든 핵심은 지금까지 어떤 정점을 방문했는지 기록하는 것이다. 기록하지 않으면 무한 사이클에 빠진다.

방문했던 정점을 기록할 한 가지 방법은 해시 테이블을 사용하는 것이다. 각 정점을 방문할 때마다 그 정점(혹은 그 정점의 값)을 키로 해서 해시 테이블에 추가하고, 값으로 true와 같은 임의의 값을 할당한다. 해시 테이블에 어떤 정점이 있다면 이미 방문했다는 뜻이다.

1. 그래프 내 임의의 정점에서 시작한다.
2. 현재 정점을 해시 테이블에 추가해 방문했던 정점임을 표시한다.
3. 현재 정점의 인접 정점을 순회한다.
4. 방문했던 인접 정점이면 무시한다.
5. 방문하지 않았던 인접 정점이면 그 정점에 대해 재귀적으로 깊이 우선 탐색을 수행한다.

18.5.1 깊이 우선 탐색 연습

위 사진과 같은 그래프에서 깊이 우선 탐색 알고리즘을 실제로 수행한다.

1. A부터 시작한다. A 정점에 방문했음을 표시한다.
   • 이어서 A의 이웃을 순회한다. A의 이웃은 B, C, D, E다. 순서는 중요하지 않으니 B부터 시작한다.
2. B에 깊이 우선 탐색을 수행한다.
   • A에 깊이 우선 탐색을 수행하던 중이었으니 재귀 호출이다. A를 먼저 호출 스택에 추가한다.
   • B가 현재 정점이 된다. B 정점에 방문했다고 표시한다.
   • 이어서 B의 인접 정점인 A와 F를 순회한다.
3. A는 이미 방문했으니 무시한다.
4. 남은 인접 정점은 F 뿐이다. F에 깊이 우선 탐색 함수를 호출한다. B를 호출 스택에 추가한다. (A > B)
   • F 정점에 방문했다고 표시한다.
   • F의 인접 정점인 B와 H를 순회한다.
5. B는 이미 방문했으니 무시한다.
6. 남은 인접 정점은 H 뿐이다. H에 깊이 우선 탐색 함수를 호출한다. F를 호출 스택에 추가한다. (A > B > F)
   • H 정점에 방문했다고 표시한다.
   • H의 인접 정점인 F와 C를 순회한다.
7. F는 이미 방문했으니 무시한다.
8. C에 깊이 우선 탐색 함수를 호출한다. H를 호출 스택에 추가한다. (A > B > F > H)
   • C 정점에 방문했다고 표시한다.
   • C의 인접 정점인 H와 A를 순회한다.
9. H는 이미 방문했으니 무시한다.
10. A도 이미 방문했으니 무시한다.
    • C에 다른 이웃이 없으니 C에 대한 깊이 우선 탐색은 여기서 끝이다. 호출 스택을 해제하기 시작한다.
    • H를 팝한다. H에 남은 이웃이 없으니 H에 대한 깊이 우선 탐색이 끝났다.
    • B를 팝한다. B 탐색도 끝났다.
    • A를 팝한다. A의 이웃엔 아직 C, D, E가 남았다.
11. C는 이미 방문했으니 무시한다.
12. D에 깊이 우선 탐색 함수를 호출한다.
    • D 정점에 방문했다고 표시한다.
    • D의 인접 정점인 A, E, G를 순회한다.
13. A는 이미 방문했으니 무시한다.
14. E에 깊이 우선 탐색 함수를 호출한다. D를 호출 스택에 추가한다. (A > D)
    • E 정점에 방문했다고 표시한다.
    • E의 인접 정점인 A, D를 순회한다.
15. A는 이미 방문했으니 무시한다.
16. D도 이미 방문했으니 무시한다.
    • E의 이웃을 모두 순회했고 E 탐색이 끝났다.
    • 호출 스택에서 D를 팝해 D의 남은 이웃 G를 순회한다.
17. G에 깊이 우선 탐색 함수를 호출한다. D를 호출 스택에 추가한다. (A > D)
    • G 정점에 방문했다고 표시한다.
    • G의 인접 정점인 D, I를 순회한다.
18. D는 이미 방문했으니 무시한다.
19. I에 깊이 우선 탐색 함수를 호출한다. G를 호출 스택에 추가한다. (A > D > G)
    • I 정점에 방문했다고 표시한다.
    • I의 인접 정점인 G를 순회한다.
20. G는 이미 방문했으니 무시한다.

각 정점을 하나씩 팝하며 호출 스택을 해제한다. 호출 스택에 있던 각 정점마다 모든 이웃을 순회했으므로 컴퓨터가 더 할 일이 없다.

18.5.2 코드 구현: 깊이 우선 탐색

dfsTraverse(vertex, visitedVertices = new Map()) {
  visitedVertices.set(vertex.value, true);
  console.log(vertex.value);

  for (let adjacentVertex of vertex.adjacentVertices) {
    if (visitedVertices.get(adjacentVertex.value)) {
      continue;
    }
    this.dfsTraverse(adjacentVertex, visitedVertices);
  }
}

메서드는 vertex 하나와 선택적으로 visitedVertices 해시 테이블을 받는다. 함수를 처음 호출할 때 visitedVertices는 비어있지만 정점을 방문할 때마다 해시 테이블을 채우면서 각 재귀 호출에 해시 테이블을 전달한다.

가장 먼저 해시 테이블에 정점의 값을 추가하면서 정점을 방문했다는 표시를 남긴다.

이후 현재 정점의 인접 정점을 for문으로 순회한다.
만일 이미 방문한 인접 정점이라면 다음 반복문으로 건너 뛴다.
방문하지 않았다면 인접 정점에 dfsTraverse를 재귀적으로 호출한다.

깊이 우선 탐색을 사용해 실제 어떤 정점을 찾고 싶으면 함수를 다음과 같이 수정한다.

dfs(vertex, searchValue, visitedVertices = new Map()) {
  // 찾고 있던 정점이면 원래의 vertex를 반환한다.
  if (vertex.value === searchValue) {
    return vertex;
  }

  visitedVertices.set(vertex.value, true);
  console.log(vertex.value);

  for (let adjacentVertex of vertex.adjacentVertices) {
    if (visitedVertices.get(adjacentVertex.value)) {
      continue;
    }

    // 인접 정점이 찾고 있던 정점이면 그 인접 정점을 반환한다.
    if (adjacentVertex.value === searchValue) {
      return adjacentVertex;
    }

    // 인접 정점에 계속해서 메서드를 재귀 호출해 찾고 있던 정점을 찾는다
    const vertexWereSearchingFor = dfs(
      adjacentVertex,
      searchValue,
      visitedVertices
    );

    // 찾았으면 그 정점을 리턴한다
    if (vertexWereSearchingFor) {
      return vertexWereSearchingFor;
    }
  }
  // 찾고 있는 정점을 못 찾으면 null을 리턴한다.
  return null;
}

재귀적으로 각 정점을 호출하되 원하는 정점을 찾으면 vertexWereSearchingFor을 리턴한다.

18.6 너비 우선 탐색

흔히 BFS(Breadth-First Search)로 부르는 너비 우선 탐색은 그래프를 탐색하는 또 다른 방법이다.

너비 우선 탐색은 재귀를 쓰지 않고 큐로 문제를 해결한다.

1. 그래프 내 아무 정점에서나 시작한다. 이 정점을 시작 정점이라 부른다.
2. 시작 정점을 해시 테이블에 추가해 방문했다고 표시한다.
3. 시작 정점을 큐에 추가한다.
4. 큐가 빌 때까지 실행하는 반복문을 시작한다.
5. 루프 안에서 큐의 첫 번째 정점을 삭제한다. 이 정점을 "현재 정점"이라 부른다.
6. 현재 정점의 인접 정점을 순회한다.
7. 이미 방문한 인접 정점이면 무시한다.
8. 아직 망문하지 않은 인접 정점이면 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.
9. 큐가 빌 때까지 반복문을 계속한다.

18.6.1 너비 우선 탐색 연습

0. A를 시작 정점으로 삼는다. A에 방문했다고 표시하고 큐에 추가한다.
1. 큐에서 첫 정점을 삭제 해 현재 정점으로 만든다. 큐에 항목이 A뿐이니 현재 정점은 A다. 큐는 비어있다.
   • A의 인접 정점을 순회한다.
2. B로 넘어간다. B에 방문했다고 표시한 후 큐에 추가한다.
   • A의 인접 정점이 남아 있으므로 현재 정점은 여전히 A다. 하지만 B에 방문했다고 표시했고, 큐에도 들어가 있다.
3. C로 넘어가 C에 방문했다고 표시한 후 큐에 추가한다. (B - C)
4. D로 넘어가 D에 방문했다고 표시한 후 큐에 추가한다. (B - C - D)
5. E로 넘어가 E에 방문했다고 표시한 후 큐에 추가한다. (B - C - D - E)
6. A의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 B를 디큐해 현재 정점으로 만든다. (C - D - E)
   • B의 인접 정점을 순회한다.
7. A는 이미 방문했으니 무시한다.
8. F로 넘어가 F에 방문했다고 표시한 후 큐에 추가한다. (C - D - E - F)
9. B의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 C를 디큐해 현재 정점으로 만든다. (D - E - F)
   • C의 인접 정점을 순회한다.
10. A는 이미 방문했으니 무시한다.
11. H로 넘어가 H에 방문했다고 표시한 후 큐에 추가한다. (D - E - F - H)
12. C의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 D를 디큐해 현재 정점으로 만든다. (E - F - H)
    • D의 인접 정점을 순회한다.
13. A는 이미 방문했으니 무시한다.
14. E도 이미 방문했으니 무시한다.
15. G로 넘어가 G에 방문했다고 표시한 후 큐에 추가한다. (E - F - H - G)
16. D의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 E를 디큐해 현재 정점으로 만든다. (F - H - G)
    • E의 인접 정점을 순회한다.
17. A는 이미 방문했으니 무시한다.
18. D는 이미 방문했으니 무시한다.
19. E의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 F를 디큐해 현재 정점으로 만든다. (H - G)
    • F의 인접 정점을 순회한다.
20. B는 이미 방문했으니 무시한다.
21. H도 이미 방문했으니 무시한다.
22. F의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 H를 디큐해 현재 정점으로 만든다. (G)
    • H의 인접 정점을 순회한다.
23. F는 이미 방문했으니 무시한다.
24. C도 이미 방문했으니 무시한다.
25. H의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 G를 디큐해 현재 정점으로 만든다.
    • G의 인접 정점을 순회한다.
26. D는 이미 방문했으니 무시한다.
27. I로 넘어가 I에 방문했다고 표시한 후 큐에 추가한다.
28. G의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 I를 디큐해 현재 정점으로 만든다.
29. I의 인접 정점은 G 하나인데 G는 이미 방문했다.
    • 큐에 더 이상 삭제할 항목이 없으므로 모두 순회했다.

18.6.2 코드 구현: 너비 우선 탐색

// 너비 우선 탐색 메서드
bfsTraverse(startingVertex) {
  const queue = new Queue();

  const visitedVertices = new Map();
  visitedVertices.set(startingVertex.value, true);
  queue.enqueue(startingVertex);

  // 큐가 빌 때까지 실행한다
  while (queue.read()) {
    const currentVertex = queue.dequeue();
    console.log(currentVertex.value);

    for (let adjacentVertex of currentVertex.adjacentVertices) {
      if (!visitedVertices.get(adjacentVertex.value)) {
        visitedVertices.set(adjacentVertex.value, true);
        queue.enqueue(adjacentVertex);
      }
    }
  }
}

// 큐 클래스
class Queue {
  constructor() {
    this.data = [];
  }
  enqueue(element) {
    this.data.push(element);
  }
  dequeue() {
    return this.data.shift();
  }
  read() {
    return this.data[0];
  }
}

알고리즘에 필요한 큐를 생성하고, 방문했던 정점을 기록할 해시 테이블도 생성한다.
startingVertex에 방문했다고 표시한 후 큐에 추가한다.

큐가 빌 때까지 실행하는 while 문을 실행한다.
큐에서 첫 항목을 디큐해 현재 정점으로 만들고, 현재 정점의 모든 인접 정점을 for 문으로 순회한다.

만일 방문하지 않은 정점에 대해 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.

18.6.3 깊이 우선 탐색 대 너비 우선 탐색

너비 우선 탐색은 시작 정점과 가장 가까운 정점을 모두 순회한 후 멀어진다.
깊이 우선 탐색은 즉시 시작 정점에서 최대한 멀어진다.

어떤 시나리오에선 깊이 우선 탐색이 빠르고, 다른 시나리오에선 너비 우선 탐색이 더 빠를 수 있다.

소셜 네트워크에서 친구의 친구가 아닌, '진짜' 친구만을 찾는다면 시작 정점과 가장 가까운 정점(즉, 진짜 친구)을 바로 찾는 너비 우선 방식이 빠를 것이다.

하지만 가계도에서 증손주를 찾아야 한다면 모든 자식과 손주를 순회하는 것이 아니라 바로 증손주에 도달하는 깊이 우선 탐색이 빠를 것이다.

그래프를 탐색하는 동안 시작 정점 가까이 있고 싶다면 너비 우선 탐색이 좋고, 시작 정점과 빨리 멀어져야 한다면 깊이 우선 탐색이 이상적이다.

18.7 그래프 탐색의 효율성

DFS, BFS 모두 최악의 시나리오에서 모든 정점을 순회한다. 최악의 시나리오는 그래프 전체를 순회하거나 존재하지 않는 정점을 찾는 경우, 그래프에서 마지막으로 확인하는 정점이 찾고 있던 정점인 경우다.

두 탐색 알고리즘은 순회하는 각 정점의 인접 정점까지 모두 순회한다. 방문했던 정점을 무시한다해도 정점을 확인하는 단계가 필요하다. 정점마다 인접 정점의 개수가 다르니 빅 오 표기법으로 딱 고정해서 말하기 어렵다.

즉 그래프 내 정점 개수만으로는 단계를 셀 수 없다. 각 정점의 인접 정점이 몇 개인지도 함께 고려 해야 한다. 따라서 변수 두 개가 필요하다. 하나는 정점 개수이고, 다른 하나는 각 정점들의 총 인접 정점 수를 나타내야 한다.

18.7.1 O(V+E)

V는 정점Vertex을 뜻하며 그래프 내 정점 수를 나타낸다.
E는 간선Edge을 뜻하며 그래프 내 간선 수를 나타낸다.

O(V+E)는 E를 한 번만 세지만 실제로 그래프 탐색에서는 각 간선을 두 번 이상 방문한다. 즉 최소 V + 2E 단계가 걸린다.
하지만 빅 오 표기법은 상수를 버리므로 O(V+E)로 표기한다.

본질적으로 근사치이지만 간선의 개수가 많아질 수록 단계 수도 늘어난다는 것엔 변함이 없다.

DFS, BFS 모두 최악의 시나리오에선 O(V+E)지만, 그래프 모양과 찾고 있는 데이터에 기반해 둘 중 하나를 선택해 탐색을 최적화할 수 있다. 적절한 탐색 메서드 선택은 최악의 시나리오로 이어질 가능성을 줄여주고, 정점을 보다 빨리 찾아준다.

18.8 가중 그래프

그래프 간선에 정보를 추가하는 가중 그래프 Weighed Graph는 그래프의 변형이다.

각 간선에 간선으로 연결된 도시 간 거리가 마일 단위 숫자로 붙어있다. 가령 시카고와 뉴욕 사이 거리는 714마일이다.

18.8.1 가중 그래프 코드

class WeightedGraphVertex {
  constructor(value) {
    this.value = value;
    this.adjacentVertices = new Map();
  }

  addAdjacentVertex(vertex, weight) {
    this.adjacentVertices.set(vertex, weight);
  }
}

adjacentVertices가 배열이 아닌 해시 테이블이다. 이 해시 테이블은 키가 인접 정점이고 값이 간선의 가중치인 키-값 쌍을 포함한다.

18.8.2 최단 경로 문제

가중 그래프는 각가지 데이터 세트를 훌륭하게 모델링하며 그 데이터를 최대한 활용하는 강력한 알고리즘까지 지원한다.

여러 도시의 항공료가 적힌 가중 그래프가 있다고 하자.
두 도시에 직항이 없다고 할 때, 경유하는 비용을 포함해 최소 비용을 찾는 알고리즘을 유형의 문제를 최단 경로 문제라 부른다.

18.9 데이크스트라의 알고리즘

최단 경로 문제를 푸는 알고리즘 중 하나가 데이크스트라의 알고리즘이다.

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

알고리즘을 모두 수행하면 아틀란타에서 엘파소로 가는 가장 저렴한 비용뿐 아니라, 아틀란타에서 모든 도시로 가는 가장 저렴한 비용을 찾게 된다.

시작 도시에서 다른 목적지까지 가는 현재까지 가장 저렴한 비용을 저장할 수단이 필요하다. 코드에선 해시 테이블을 사용하고, 연습 예제에선 표를 사용한다.

아틀란타부터	1번 도시	2번 도시	3번 도시	그 외
	?	?	?	?

현재 유일하게 알려진 도시인 아틀란타 정점에서 시작한다. 새 도시를 발견하면 표에 추가 하고 아틀란타에서 각 도시까지의 최소 비용을 기록한다. 알고리즘을 모두 수행하고 나면 표는 다음과 같다.

아틀란타부터	보스턴	시카고	덴버	엘 파소
	100	200	160	280

해시 테이블로 나타내면 다음과 같다.

{'아틀란타' => 0, '보스턴' => 100, '시카고' => 200, '덴버' => 160, '엘 파소' => 280}

앞으로 이 표를 cheapestPricesTable이라 부른다. 특정 도시까지의 가장 저렴한 비용은 표를 보면 된다. 하지만 실제 경로를 알려면 새 표인 cheapestPreviousStopoverCityTable이 필요하다. 이 표는 알고리즘 종료 후 다음과 같다.

아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴	시카고	덴버	엘 파소
	아틀란타	덴버	아틀란타	시카고

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

도시라는 단어로 설명하나 도시를 정점으로 바꾸면 어떤 가중 그래프에든 적용 가능하다.

1. 시작 도시에 방문해 현재 도시로 만든다.
2. 현재 도시에서 각 인접 도시로의 비용을 확인한다.
3. 시작 도시에서 인접 도시로의 비용이 현재 chepeastPricesTable의 비용보다 저렴하면 (혹은 인접도시가 아직 cheapestPricesTable에 없으면)
   1. chepestPricesTable을 더 저렴한 비용으로 업데이트한다.
   2. 인접 도시를 키로, 현재 도시를 값으로 해서 cheapestPreviousStopoverCityTable을 업데이트 한다.
4. 다음으로 시작 도시에서 방문하지 않은 도시 중 비용이 가장 저렴한 도시에 방문해 현재 도시로 만든다.
5. 알려진 도시에 모두 방문할 때까지 2-4단계를 반복한다.

18.9.3 데이크스트라의 알고리즘 연습

cheapestPricesTable에 아틀란타를 넣으며 시작한다.

1. 아틀란타를 currentCity로 지정한다.

2. 아틀란타에서 보스턴까지의 비용은 100달러이다. cheapestPricesTable에 아직 기록되지 않았으므로 추가한다.

   • 아틀란타부터	보스턴
     	100

   • cheapestPreviousStopoverCityTable도 업데이트 한다.

   • 아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴
     	아틀란타

3. 아틀란타에서 덴버까지의 비용은 160달러이다. 표에 아직 기록되지 않았으므로 추가한다.

   • 아틀란타부터	보스턴	덴버
     	100	160

   • cheapestPreviousStopoverCityTable도 업데이트 한다.

   • 아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴	덴버
     	아틀란타	아틀란타

4. 아틀란타의 인접 도시를 모두 확인했다. 방문하지 않은 도시 중 가장 저렴한 도시인 보스턴을 방문한다.

5. 보스턴을 currentCity로 지정한다.

6. 보스턴에서 시카고까지의 비용은 120달러, 아탈란타로부터는 220달러다. cheapestPricesTable에 아직 기록되지 않았으므로 추가한다.

   • 아틀란타부터	보스턴	시카고	덴버
     	100	220	160

   • cheapestPreviousStopoverCityTable도 업데이트 한다.

   • 아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴	시카고	덴버
     	아틀란타	보스턴	아틀란타

7. 보스턴에서 덴버까지의 비용은 180달러, 아틀란타로부터는 280달러다. 표에 적힌 비용보다 더 비싸므로 표를 수정하지 않는다.

8. 보스턴의 인접 도시를 모두 확인했다. 방문하지 않은 도시 중 가장 저렴한 도시인 덴버를 방문해 currentCity로 지정한다.

9. 덴버에서 시카고까지의 비용은 40달러, 아탈란타로부터는 200달러다. 표에 적힌 비용보다 더 저렴하므로 표를 수정한다.

   • 아틀란타부터	보스턴	시카고	덴버
     	100	200	160

   • cheapestPreviousStopoverCityTable도 업데이트 한다.

   • 아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴	시카고	덴버
     	아틀란타	덴버	아틀란타

10. 덴버에서 엘 파소까지의 비용은 140달러, 아틀란타로부터는 300달러다. 표에 아직 기록되지 않았으므로 추가한다.

    • 아틀란타부터	보스턴	시카고	덴버	엘 파소
      	100	200	160	300

    • cheapestPreviousStopoverCityTable도 업데이트 한다.

    • 아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴	시카고	덴버	엘 파소
      	아틀란타	덴버	아틀란타	덴버

11. 덴버의 인접 도시를 모두 확인했다. 방문하지 않은 도시 중 가장 저렴한 도시인 시카고를 방문해 currentCity로 지정한다.

12. 시카고에서 엘 파소까지의 비용은 80달러, 아탈란타로부터는 280달러다. 표에 적힌 비용보다 더 저렴하므로 표를 수정한다.

    • 아틀란타부터	보스턴	시카고	덴버	엘 파소
      	100	200	160	280

    • cheapestPreviousStopoverCityTable도 업데이트 한다.

    • 아틀란타부터 최소 비용으로 가는 직전 경유지	보스턴	시카고	덴버	엘 파소
      	아틀란타	덴버	아틀란타	시카고

13. 시카고의 인접 도시를 모두 확인했다. 방문하지 않은 도시인 엘 파소를 방문에 currentCity로 지정한다.

14. 엘 파소에서 보스턴까지의 비용은 100달러, 아틀란타로부터는 380달러다. 표에 적힌 비용보다 더 비싸므로 표를 수정하지 않는다.

18.9.4 최단 경로 찾기

아틀란타에서 엘 파소로 가는 가장 저렴한 비용을 알고 싶을 때 cheapestPricesTable를 보면 280달러를 확인할 수 있다. 경로를 확인하려면 cheapestPreviousStopoverCityTable를 확인해야 한다.

아틀란타에서 가장 저렴하게 엘 파소를 가기 위해 직전 경유해야 하는 곳은 시카고이다. (시카고 - 엘 파소)
아틀란타에서 가장 저렴하게 시카고를 가기 위해 직전 경유해야 하는 곳은 덴버다. (덴버 - 시카고 - 엘 파소)
아틀란타에서 가장 저렴하게 덴버를 가기 위해 직전 경유해야 하는 곳은 아틀란타, 즉 직항이다. (아틀란타 - 덴버 - 시카고 - 엘 파소)

즉, 아틀란타 - 덴버 - 시카고 - 엘 파소가 가장 저렴한 경로이다.

18.9.5 코드 구현: 데이크스트라의 알고리즘

18.9.3의 예제를 구성하기 위해 City 클래스를 새로 만들었다.

class City {
  constructor(name) {
    this.name = name;
    this.routes = new Map();
  }

  addRoute(city, price) {
    this.routes.set(city, price);
  }
}

atlanta = new City("atlanta");
boston = new City("boston");
chicago = new City("chicago");
denver = new City("denver");
elPaso = new City("elPaso");

atlanta.addRoute(boston, 100);
atlanta.addRoute(denver, 160);
boston.addRoute(chicago, 120);
boston.addRoute(denver, 180);
chicago.addRoute(elPaso, 80);
denver.addRoute(chicago, 40);
denver.addRoute(elPaso, 140);

데이크스트라의 알고리즘 코드는 City 클래스 밖에 두고, 두 City 인스턴스를 받아 둘 사이의 최단 경로를 반환한다.

function dijkstraShortestPath(startingCity, finalDestination) {
  const cheapestPricesTable = new Map();
  const cheapestPreviousStopoverCityTable = new Map();

  // 코드가 복잡해지지 않도록
  // 아직 방문하지 않은 알려진 도시를 단순 배열에 기록한다.
  const unvisitedCities = [];

  // 방문했던 도시를 효율적으로 룩업하기 위해 해시 테이블에 기록한다.
  const visitedCities = new Map();

  // cheapestPricesTable의 첫 키로 시작 도시의 이름을 추가한다.
  cheapestPricesTable.set(startingCity, 0);
  let currentCity = startingCity;

  //방문하지 않은 도시가 남아있는 동안 실행된다.
  while (currentCity) {
    // visitedCities에 방문했음을 기록한다
    // unvisitedCities에서 제거한다
    visitedCities.set(currentCity.name, true);
    unvisitedCities.splice(unvisitedCities.indexOf(currentCity), 1);

    // currentCity의 인접 도시를 순회한다.
    for (let [adjacentCity, price] of currentCity.routes) {
      // 새 도시를 발견하면 unvisitedCities 리스트에 추가한다.
      if (!visitedCities.get(adjacentCity.name)) {
        unvisitedCities.push(adjacentCity);
      }

      // currentCity를 마지막으로 경유하는 도시로 사용해
      // startingCity에서 adjacentCity로 가는 비용을 계산한다.
      const priceThroughCurrentCity =
        cheapestPricesTable.get(currentCity) + price;

      // startingCity에서 adjacentCity로 가는 비용이
      // 지금까지 알려진 비용보다 저렴하면
      if (
        !cheapestPricesTable.get(adjacentCity) ||
        priceThroughCurrentCity < cheapestPricesTable.get(adjacentCity)
      ) {
        // 두 표를 업데이트 한다.
        cheapestPricesTable.set(adjacentCity, priceThroughCurrentCity);
        cheapestPreviousStopoverCityTable.set(
          adjacentCity.name,
          currentCity.name
        );
      }
    }

    // 방문하지 않은 다음 도시를 방문한다
    // startingCity에서 갈 수 있는 가장 저렴한 도시로 선택한다.
    let willBeSortedPrice = [];
    let reversedCheapestPricesTable = new Map();
    for (let city of unvisitedCities) {
      // unvisitedCities를 순회하면서 가격을 willBeSortedPrice에 추가한다.
      // reversedCheapestPricesTable에는 가격을 키로, 도시를 값으로 하는 키값쌍을 추가한다.
      willBeSortedPrice.push(cheapestPricesTable.get(city));
      reversedCheapestPricesTable.set(cheapestPricesTable.get(city), city);
    }
    // 가장 저렴한 가격을 찾아 그 가격을 키로 하는 도시를 찾아
    // currentCity에 할당한다.
    const cheapestPrice = Math.min(...willBeSortedPrice);
    currentCity = reversedCheapestPricesTable.get(cheapestPrice);
  }

  // 이제 cheapestPricesTable은 startingCity에서
  // 각 도시로 가는 가장 저렴한 비용을 모두 포함한다.
  // 최단 경로를 계산하는 코드를 작성한다.
  const shortestPath = [];

  // finalDestination에서 거슬러 올라간다.
  let currentCityName = finalDestination.name;
  // startingCity에 도달할 때까지 반복문을 실행한다.
  while (currentCityName !== startingCity.name) {
    shortestPath.push(currentCityName);
    currentCityName = cheapestPreviousStopoverCityTable.get(currentCityName);
  }
  // 마지막으로 startingCity를 추가한다.
  shortestPath.push(startingCity.name);
  return shortestPath.reverse();
}

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

방문하지 않은 도시를 단순 배열에 저장하면 알고리즘에 최대 O(V²) 단계가 걸린다.

배열 대신 우선순위 큐로 구현하면 속도가 더 빠르다. 데이크스트라의 알고리즘에는 많은 변형이 있고 각 변형마다 시간 복잡도가 다르다.

하지만 어떻게 구현하든 최단 거리를 구하는 다른 대안보다는 빠르다.

18.10 마무리

그래프는 관계를 포함하는 데이터를 처리할 때 매우 강력한 도구이며, 코드 속도를 높임과 동시에 까다로운 문제를 푸는데 도움이 될 수 있다.