그래프와 탐색

그래프란

트리는 계층 구조를 표현하는 자료구조였습니다. 하지만 현실의 많은 관계는 계층이 아닌 네트워크 형태입니다. 소셜 네트워크의 친구 관계, 도시 간 도로, 웹 페이지 간의 하이퍼링크가 대표적입니다.

**그래프 (Graph)**는 **노드 (정점, Vertex)**와 **간선 (Edge)**으로 구성된 자료구조입니다. 트리도 그래프의 특수한 형태 (사이클이 없는 연결 그래프)입니다.

그래프의 종류

**방향 그래프 (Directed Graph)**는 간선에 방향이 있습니다. 트위터의 팔로우 관계가 대표적입니다. A가 B를 팔로우해도 B가 A를 팔로우하지 않을 수 있습니다.

방향 그래프:           무방향 그래프:
A --> B               A --- B
      |                     |
C --> D               C --- D

**무방향 그래프 (Undirected Graph)**는 간선에 방향이 없습니다. 페이스북의 친구 관계가 대표적입니다. A와 B가 친구이면 양방향입니다.

**가중 그래프 (Weighted Graph)**는 간선에 가중치 (비용, 거리 등)가 있습니다. 도시 간 도로의 거리, 네트워크 대역폭 등을 표현합니다.

가중 그래프:

A --5-- B
        |
A --3-- C --4-- D --2-- B

핵심 용어

정점 (Vertex) : 그래프의 노드
간선 (Edge) : 두 정점을 연결하는 선
인접 (Adjacent) : 간선으로 직접 연결된 두 정점
차수 (Degree) : 한 정점에 연결된 간선의 수
경로 (Path) : 정점의 나열로, 연속된 정점이 간선으로 연결
사이클 (Cycle) : 시작 정점과 끝 정점이 같은 경로

그래프 표현

그래프를 코드로 표현하는 방법은 크게 두 가지입니다.

인접 리스트 (Adjacency List)

각 정점에 대해 연결된 정점의 리스트를 저장합니다. 공간 효율적 이고, 대부분의 실무 그래프에서 사용합니다.

// 인접 리스트 - 객체(해시맵) 사용
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "E", "F"],
  D: ["B"],
  E: ["B", "C", "G"],
  F: ["C"],
  G: ["E"],
};

// Map 사용 (더 안전한 방식)
const graphMap = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D", "E"]],
  ["C", ["A", "E", "F"]],
  ["D", ["B"]],
  ["E", ["B", "C", "G"]],
  ["F", ["C"]],
  ["G", ["E"]],
]);

인접 행렬 (Adjacency Matrix)

정점 간 연결을 2차원 배열로 표현합니다. matrix[i][j] = 1이면 정점 i와 j가 연결되어 있습니다.

// 인접 행렬 (A=0, B=1, C=2, D=3)
//       A  B  C  D
const matrix = [
  [0, 1, 1, 0], // A
  [1, 0, 0, 1], // B
  [1, 0, 0, 1], // C
  [0, 1, 1, 0], // D
];

// matrix[0][1] === 1 → A와 B는 연결됨
// matrix[0][3] === 0 → A와 D는 연결 안 됨

비교

특성	인접 리스트	인접 행렬
공간 복잡도	O(V + E)	O(V^2)
간선 존재 확인	O(degree)	O(1)
모든 이웃 탐색	O(degree)	O(V)
간선 추가	O(1)	O(1)
적합한 경우	희소 그래프 (간선 적음)	밀집 그래프 (간선 많음)
실무 사용 빈도	높음	낮음

대부분의 실무 그래프는 희소 그래프 (정점 수에 비해 간선이 적은)이므로 인접 리스트가 표준입니다. 소셜 네트워크를 예로 들면, 사용자가 10억 명이어도 한 사람의 친구는 수백~수천 명에 불과합니다. 인접 행렬로 표현하면 10억 x 10억 = 10^18 크기의 배열이 필요하지만, 인접 리스트는 실제 간선 수만큼만 공간을 사용합니다.

BFS (너비 우선 탐색)

BFS (Breadth-First Search)는 시작 정점에서 가까운 정점부터 탐색하는 알고리즘입니다. **큐 (Queue)**를 사용하며, 레벨별로 탐색합니다.

의사코드

BFS(graph, start):
    queue = [start]
    visited = {start}

    while queue is not empty:
        node = queue.dequeue()        // 큐 앞에서 꺼냄 (FIFO)
        process(node)

        for each neighbor of node:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor) // 큐 뒤에 추가

핵심: 큐의 FIFO (First-In, First-Out) 특성 덕분에, 먼저 발견된 (가까운) 노드가 먼저 처리됩니다.

JavaScript 구현

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift(); // 큐 앞에서 꺼냄
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor); // 큐 뒤에 추가
      }
    }
  }

  return order;
}

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "E", "F"],
  D: ["B"],
  E: ["B", "C", "G"],
  F: ["C"],
  G: ["E"],
};

console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "E", "F", "G"]

시간 복잡도는 O(V + E)입니다. 모든 정점을 한 번씩 방문하고 (V), 모든 간선을 한 번씩 확인합니다 (E).

참고 : Array.shift()는 O(n)이므로 대규모 그래프에서는 별도의 큐 자료구조를 사용하는 것이 좋습니다. 이전 글의 스택과 큐 구현을 활용할 수 있습니다.

BFS 시각화

아래 시각화에서 BFS가 큐를 사용해 레벨별로 탐색하는 과정을 확인하세요. 큐 상태와 방문 순서에 주목합니다.

초기 상태1 / 9

큐:

현재 노드방문 완료대기 중

7개의 노드와 7개의 간선으로 구성된 무방향 그래프입니다. 노드 A에서 BFS를 시작합니다. 큐에 시작 노드를 넣습니다.

DFS (깊이 우선 탐색)

DFS (Depth-First Search)는 한 경로를 끝까지 탐색한 후 되돌아오는 알고리즘입니다. 스택 (Stack) 또는 재귀를 사용합니다.

의사코드

DFS-Stack(graph, start):
    stack = [start]
    visited = {}

    while stack is not empty:
        node = stack.pop()            // 스택 위에서 꺼냄 (LIFO)
        if node in visited: continue
        visited.add(node)
        process(node)

        for each neighbor of node:
            if neighbor not in visited:
                stack.push(neighbor)  // 스택 위에 추가

DFS-Recursive(graph, node, visited):
    visited.add(node)
    process(node)

    for each neighbor of node:
        if neighbor not in visited:
            DFS-Recursive(graph, neighbor, visited)

핵심: 스택의 LIFO (Last-In, First-Out) 특성 때문에, 가장 최근에 발견된 (깊은) 노드가 먼저 처리됩니다. 재귀 방식은 콜 스택이 암묵적으로 스택 역할을 합니다.

JavaScript 구현

// 스택 기반 DFS
function dfsStack(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop(); // 스택 위에서 꺼냄
    if (visited.has(node)) continue;

    visited.add(node);
    order.push(node);

    // 이웃을 역순으로 추가 (원래 순서대로 탐색하려면)
    for (const neighbor of [...graph[node]].reverse()) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }

  return order;
}

// 재귀 기반 DFS
function dfsRecursive(graph, start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);

  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited, order);
    }
  }

  return order;
}

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "E", "F"],
  D: ["B"],
  E: ["B", "C", "G"],
  F: ["C"],
  G: ["E"],
};

console.log(dfsStack(graph, "A"));
// ["A", "B", "D", "E", "C", "F", "G"]

console.log(dfsRecursive(graph, "A"));
// ["A", "B", "D", "E", "C", "F", "G"]

시간 복잡도는 BFS와 동일하게 O(V + E)입니다.

참고 : 재귀 DFS와 스택 DFS의 방문 순서가 다를 수 있습니다. 이웃을 처리하는 순서가 다르기 때문입니다. 둘 다 정당한 DFS입니다.

DFS 시각화

아래 시각화에서 DFS가 스택을 사용해 한 경로를 끝까지 파고드는 과정을 확인하세요. BFS와 방문 순서가 어떻게 다른지 비교해 봅니다.

초기 상태1 / 9

스택:

현재 노드방문 완료대기 중

같은 그래프에서 이번에는 DFS를 시작합니다. 노드 A에서 출발합니다. 스택에 시작 노드를 넣습니다.

BFS vs DFS 비교

특성	BFS	DFS
자료구조	큐 (FIFO)	스택/재귀 (LIFO)
탐색 방식	레벨별 (넓게)	경로별 (깊게)
시간 복잡도	O(V + E)	O(V + E)
공간 복잡도	O(V), 최악의 경우 한 레벨의 모든 노드	O(V), 최악의 경우 경로 길이만큼
최단 경로 보장	가중치 없는 그래프에서 보장	보장하지 않음
적합한 경우	최단 경로, 레벨별 탐색	경로 존재 여부, 사이클 감지, 위상 정렬

언제 BFS를 쓰는가

최단 경로 : 미로에서 출구까지 최단 거리를 찾을 때
레벨별 탐색 : 소셜 네트워크에서 1촌, 2촌, 3촌을 구분할 때
가까운 노드 우선 : 게임에서 주변 범위 내 적을 탐색할 때

언제 DFS를 쓰는가

경로 존재 여부 : 두 노드 사이에 경로가 있는지 확인할 때
사이클 감지 : 의존성 그래프에서 순환 참조를 찾을 때
위상 정렬 : 작업 순서를 결정할 때 (빌드 시스템, 과목 선수 관계)
미로 생성 : 무작위 DFS로 미로를 만들 때

실무 연결

npm 의존성 그래프

npm install을 실행하면 npm은 의존성 그래프를 탐색합니다. 패키지 A가 B와 C에 의존하고, B가 D에 의존하면:

my-app
  react (B)
    loose-envify (D)
    scheduler (E)
  next (C)
    react (B)    <-- 이미 방문! 중복 설치 방지
    postcss (F)

npm은 BFS/DFS를 사용해 모든 의존성을 탐색하고, 중복을 감지해 node_modules를 최적화합니다. npm ls 명령어로 이 그래프를 직접 확인할 수 있습니다.

웹 크롤링

검색 엔진의 크롤러는 웹 페이지를 그래프로 봅니다. 각 페이지가 노드, 하이퍼링크가 간선입니다. BFS를 사용하면 시작 페이지에서 가까운 페이지부터 크롤링합니다. 중요한 페이지일수록 많은 링크로 연결되어 있어 빨리 발견됩니다.

소셜 네트워크 추천

"알 수도 있는 친구" 기능은 BFS로 구현할 수 있습니다. 현재 사용자에서 BFS를 2~3단계 수행하면, 직접 친구가 아닌 친구의 친구를 찾을 수 있습니다. 공통 친구가 많을수록 추천 점수가 높아집니다.

function suggestFriends(graph, user) {
  const friends = new Set(graph[user]);
  const suggestions = new Map(); // 후보 -> 공통 친구 수
  const visited = new Set([user, ...friends]);
  const queue = [...friends];

  while (queue.length > 0) {
    const friend = queue.shift();
    for (const fof of graph[friend]) {
      if (!visited.has(fof)) {
        visited.add(fof);
        const mutual = graph[fof].filter((n) => friends.has(n)).length;
        suggestions.set(fof, mutual);
      }
    }
  }

  // 공통 친구 수가 많은 순서로 정렬
  return [...suggestions.entries()]
    .sort((a, b) => b[1] - a[1])
    .map(([user, count]) => ({ user, mutualFriends: count }));
}

다음 단계

그래프 탐색은 자료구조의 "활용" 단계입니다. 배열에서 시작해 링크드 리스트, 스택/큐, 해시맵, 트리, 그래프까지 자료구조의 핵심을 모두 다뤘습니다.

다음 글에서는 데이터를 정렬하는 알고리즘을 다룹니다. 버블 정렬부터 퀵 정렬까지, 각 알고리즘이 데이터를 어떻게 움직이는지 시각화합니다.