그래프

그래프란 노드와 간선으로 이루어진 자료구조를 의미한다.

다른 자료구조와 비교하면

1. 링크드 리스트 : NextNode (혹은 PrevNode와 NextNode)라는 포인터를 가지고 있다.
2. 트리 : 하나의 부모 노드가 여러개의 자식 노드를 가진다.
3. 그래프 : 여러개의 노드가 여러개의 간선을 가진다.

즉 링크드 리스트가 1:1, 트리가 1:N, 그래프가 N:M에 대응되는 자료구조라 할 수 있다.

그래프의 표현

그래프를 표현하는 방법은 다음과 같다.

1. 간선 리스트(edge list) : 각 간선이 어떠한 노드를 연결하는지를 튜플로 표현한다. 자바스크립트에서는 튜플 대신 배열. [[0,0], [0,4], [1,2], [1,4], [2,3], [3,4]]
2. 인접 행렬(adjacency matrix) : 노드 간의 관계를 행렬로 표현한다. (i, j)는 간선 i와 j간의 관계를 의미한다. 무방향성 그래프의 경우 대칭 형태가 된다.

[[1, 0, 0, 0, 1],
[0, 0, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[1, 1, 0, 1, 0]]

3. 인접 리스트(adjacency list) : 노드가 가진 간선들을 연결 리스트로 표현한다. i는 노드 i가 가진 간선을 의미하며, 각 값j는 노드 i와 연결된 노드 번호를 의미한다.

[[0, 4],
[2, 4],
[1, 3],
[2, 4],
[0, 1, 3]]

그래프의 방향성, 단방향 그래프(Driected Graph)

그래프는 단방향 그래프와 양방향 그래프(무방향 그래프)가 있다.

지금까지의 예시는 양방향 그래프였다. 만일 [[0,0], [0,4], [1,2], [1,4], [2,3], [3,4]]가 단방향 그래프였다면, 간선 리스트의 각 요소 [s, e]에서 s는 출발지점, e는 도착지점을 의미한다.

위와 같은 그림이 되고, 이에 따라 인접 행렬과 인접 리스트는 '갈 수 있는 노드'를 의미하며, 그 값들이 다르게 표현된다.

[[1, 0, 0, 0, 1],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0]]

[[0, 4],
[2, 4],
[3],
[4],
[]]

양방향 그래프일 때와 달리, 4번 노드는 갈 수 있느 노드가 없어서 비어있는 배열 등으로 표현되는 것을 볼 수 있다.

그래프와 가중치, 가중 그래프(Weighted Graph)

각 간선에 가중치를 입력할 수 있다.
그래프가 양방향 그래프라고 한다면, 간선 리스트의 요소는 [i, j, w]로 표현되고 i와 j는 연결하는 노드, w는 가중치(weight)를 의미한다.
[[0,0, 3], [0,4, 5], [1,2, 8], [1,4, 6], [2,3, 9], [3,4, 7]]

인접 행렬의 경우, 해당 가중치를 각 위치에 입력하는 것으로 표현할 수 있다.

[[3, 0, 0, 0, 5],
[0, 0, 8, 0, 6],
[0, 8, 0, 9, 0],
[0, 0, 9, 0, 7],
[5, 6, 0, 7, 0]]

인접 리스트의 경우에는 각 요소를 (노드번호, 가중치) 형태의 튜플로 저장할 수 있다. (역시나 튜플 대신 배열)

[[[0, 3], [4,5]],
[[2, 8], [4, 6]],
[[1, 8], [3,9]],
[[2, 8], [4, 7]],
[[0, 5], [1, 6], [3, 7]]]

탐색 알고리즘

BFS(Breadth-First Search)

BFS는 너비 우선 탐색이다. '깊이'를 기준으로, 같은 깊이를 가진 모든 노드들을 탐색해 나간다.
BFS를 구현하는 방법은 간단하다.

1. 큐를 만든다.
2. 시작 노드를 큐에 넣는다.
3. 큐에서 노드를 하나 꺼내고, 연결된 모든 노드를 큐에 넣는다.
4. 3을 계속 반복한다.

위의 과정에서
이미 방문한 노드를 다시 방문하지 않기 위한 visited라는 set,
해당 노드가 몇번째 깊이인지를 파악하기 위핸 rank라는 int 등이 추가로 활용될 수 있다.

BFS는 최단경로 찾기 알고리즘에서 유용하게 사용된다.
가령, i에서 j까지의 최단경로는 j라는 노드가 최초로 탐색되었을 때의 rank이다.
한편 트리에서의 이진탐색도 BFS의 일종이다.

아래는 미로찾기 문제의 답이다.
해당 문제는 행렬의 상, 하, 좌, 우를 연결된 노드로 하고,
입구를 시작노드, 출구를 도착노드로하여 도착 노드가 최초로 탐색되었을 때의 rank를 출력하는 대표적인 BFS문제이다.

function findPath(maze) {
  const n = maze.length;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 동서남북으로 이동하기 위한 방향 배열
  const visited = new Array(n).fill().map(() => new Array(n).fill(false)); // 방문 여부를 저장하는 배열
  const queue = [[0, 0, 0]]; // BFS를 위한 큐. 시작점 (0, 0)에서 시작하기 때문에 초기값은 [0, 0, 0]이다.

  while (queue.length > 0) {
    const [x, y, dist] = queue.shift(); // 큐에서 좌표와 거리를 꺼낸다.

    if (x === n-1 && y === n-1) { // 도착점에 도달했을 때 거리를 반환한다.
      return dist;
    }

    for (const [dx, dy] of directions) { // 동서남북으로 이동한다.
      const nx = x + dx;
      const ny = y + dy;

      if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 범위를 벗어나는 경우 건너뛴다.
      if (maze[nx][ny] === 0 || visited[nx][ny]) continue; // 벽이거나 이미 방문한 경우 건너뛴다.

      visited[nx][ny] = true; // 방문 여부를 체크하고, 큐에 좌표와 거리를 추가한다.
      queue.push([nx, ny, dist+1]);
    }
  }

  return -1; // 도착점에 도달하지 못한 경우 -1을 반환한다.
}

// 예시 미로
const maze = [
  [1, 0, 1, 1, 1],
  [1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1],
  [1, 0, 1, 0, 1],
  [1, 1, 1, 0, 1]
];

console.log(findPath(maze)); // 출력 결과: 8

DFS(Depth-First Search)

DFS는 깊이 우선 탐색이다.
자신과 연결된 노드 중 방문하지 않은 노드가 있다면 해당 노드로 이동한다. 따라서 너비를 넓히기 전에 깊이가 깊어지게 된다.

아래와 같이 구현한다.

1. 스택과 visited라는 set을 만든다.
2. 시작 노드를 스택과 visited에 넣는다.
3. 스택의 Top에서 연결된 노드 하나를 스택에 넣는다.
4. 3을 반복하며, 만일 연결된 노드가 없는 경우 Top를 pop한다.

스택 자료구조를 사용하는데, 알다시피 '재귀함수'는 '콜 스택'이라는 스택 자료구조를 이용해 호출된다. 한편 호출 순서에 따라 순회의 순서가 달라질 수 있다. 아래는 재귀함수를 이용하여 DFS를 구현한 예시이다.

function dfs(node, visited, graph) {
  visited[node] = true;
  console.log(node);

  for (const nextNode of graph[node]) {
    if (!visited[nextNode]) {
      dfs(nextNode, visited, graph);
    }
  }
}

// 시작 노드를 1로 설정한 예시
const graph = {
  1: [2, 3],
  2: [1, 4, 5],
  3: [1, 6],
  4: [2],
  5: [2, 6],
  6: [3, 5]
};
const visited = new Array(7).fill(false); // 0번 인덱스는 사용하지 않음
dfs(1, visited, graph);

BFS와 DFS의 비교

BFS는 큐와 while 반복문을 이용한다.
DFS는 스택과 재귀함수를 이용한다.

BFS는 가중치가 없는 그래프의 탐색에서 기초적으로 사용할 수 있는 알고리즘이다. 특히나 상, 하, 좌, 우 등을 탐색하는 시뮬레이션 유형의 문제에서 가중치가 없는 경우에 사용된다. 즉 '구현' 문제의 기초적인 알고리즘이다. 한편 큐와 while문을 사용하여 탐색을 한다는 아이디어 자체는 다른 알고리즘에서 많이 활용된다.

DFS는 가중치가 있는 그래프 탐색을 구현하는 데에 다양하게 사용될 수 있다. 대표적으로 다익스트라 알고리즘이 DFS를 통해 구현될 수 있다. 그 밖에 탐색이 목적이 아닌 '순회'가 목적이라면 BFS에 비해서 적은 수의 노드만을 탐색하면서 순회를 완료할 수 있다. 대표적으로 최소신장트리(Minimum Spanning Tree, MST)를 찾는 크루스칼 알고리즘, 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 문제 등도 DFS를 이용한 순회로 구현할 수 있다.