그래프: 세상의 모든 관계

프롤로그 - "트리가 아니면 뭐죠?"

개발 초기, 경험 많은 개발자가 물었습니다:

"페이스북 친구 관계를 자료구조로 표현하려면?"

저: "트리요?"

시니어: "트리는 부모-자식이 명확한데, 친구는 누가 부모야?"

저: "..."

시니어: "그래프 써야지. 친구 관계는 계층이 없어. A가 B의 친구면, B도 A의 친구지. 이건 양방향이야. 트리처럼 위에서 아래로만 흐르는 게 아니라고."

저: "그럼... 배열로?"

시니어: "배열은 순서가 있잖아. 친구에 순서가 있어? 그리고 철수가 영희 친구인지 확인하려면 어떻게 할 건데? 전체를 뒤져야 하잖아."

그때 저는 깨달았습니다. 관계를 표현하는 건 생각보다 복잡하구나.

트리는 조직도나 파일 시스템처럼 명확한 계층 구조가 있을 때 쓰는 거였습니다. 하지만 세상 대부분의 관계는 그렇게 단순하지 않았습니다. 친구 관계, 도로망, 웹페이지의 링크들... 이런 건 트리로 표현할 수 없었습니다.

왜 공부하게 되었나

회사에서 "추천 시스템" 만들라는 업무를 받았습니다.

요구사항:

• "이 상품을 본 사람은 이것도 봤어요"
• "함께 구매한 상품"
• "비슷한 관심사를 가진 사용자 추천"

저: "SQL JOIN으로 하면 되죠? 상품 테이블이랑 구매 테이블을..."

시니어: "그건 그래프 문제야. 3단계 이상 관계 따라가면 JOIN 지옥 된다. Neo4j 같은 그래프 DB 써봐. Cypher 쿼리 하나로 끝나."

저: "그래프 DB요? 들어본 적도 없는데..."

그때부터 그래프를 진지하게 공부했습니다. 단순히 이론만 배운 게 아니라, 실제로 추천 시스템을 만들면서 왜 그래프가 필요한지 몸으로 느꼈습니다.

처음엔 뭐가 이해가 안 갔나

처음에 저를 혼란스럽게 만든 것들:

1. 트리도 그래프라고?

• 교재에서 "트리는 특수한 그래프"라는 문장을 보고 멘붕
• 그럼 그래프가 더 일반적인 건데 왜 트리를 먼저 배웠지?
• 나중에 이해했습니다: 트리가 더 쉬워서 먼저 배우는 거였습니다

2. 방향/무방향이 뭐가 중요해?

• "그냥 선으로 연결하면 되는 거 아냐?"
• 트위터 팔로우 시스템 만들다가 이해했습니다
• 내가 누군가를 팔로우한다고 그 사람도 나를 팔로우하는 건 아니구나

3. 왜 행렬이랑 리스트 두 가지 방법이 있어?

• "하나만 쓰면 안 돼?"
• 성능 차이를 체감하고 나서야 받아들였습니다
• 인플루언서 10,000명 팔로워 관계를 행렬로 저장하려니 메모리가...

무엇보다 "도대체 어디에 쓰는 거야?" 라는 의문이 가장 컸습니다. 이론만 배우다 보니 실제 감각이 없었습니다.

깨달음의 순간 - "세상은 관계다"

시니어의 설명이 모든 걸 바꿔놨습니다:

"세상 모든 것은 연결되어 있어.

• 사람 ↔ 사람 (친구, 팔로우, 멘토링)
• 도시 ↔ 도시 (도로, 항공편, 철도)
• 웹페이지 ↔ 웹페이지 (하이퍼링크)
• 상품 ↔ 상품 (함께 구매됨)
• 모듈 ↔ 모듈 (의존성, import)

이 '연결'을 표현하는 게 그래프야.

트리는 특수한 그래프:

• 사이클 없음
• 부모 1명
• 계층 구조 명확

그래프는 자유로움:

• 사이클 OK (순환 참조 가능)
• 부모 여럿 OK (다중 관계)
• 복잡한 네트워크 표현 가능"

"아, 그래프가 더 일반적이구나!"

그 순간 제 머릿속에서 퍼즐이 맞춰졌습니다. 구글 검색의 PageRank 알고리즘도 그래프, LinkedIn의 "회원님이 알 수도 있는 사람"도 그래프, 카카오맵의 최단 경로도 그래프였습니다.

1. 정점(Vertex)과 간선(Edge) - 기본 개념

그래프의 핵심은 단순합니다:

정점 (Vertex/Node): 점, 객체, 엔티티
예: 사람, 도시, 웹페이지, 상품, 공항

간선 (Edge): 선, 관계, 연결
예: 친구, 도로, 링크, 구매 패턴, 항공편

이 단순한 조합만으로도 엄청나게 복잡한 시스템을 표현할 수 있습니다. 페이스북 전체가 사실 거대한 그래프입니다. 30억 명의 사용자가 정점이고, 친구 관계가 간선입니다.

2. 그래프 종류 - 상황에 맞는 선택

무방향 그래프 (Undirected Graph)

A ─ B
│   │
C ─ D

A-B 관계 = B-A 관계 (양방향)
예: 페이스북 친구, 협업 관계

특징:

• 양방향 관계
• 간선에 방향성 없음
• 대칭적 관계 표현

실제 사례:

• Facebook 친구: 철수가 영희 친구면, 영희도 철수 친구
• 공동 작업: A와 B가 함께 일하면 양방향 협업
• 네트워크 케이블: 데이터가 양방향 전송

방향 그래프 (Directed Graph / Digraph)

A → B
↑   ↓
C ← D

A→B ≠ B→A
예: 트위터 팔로우, 웹 링크, 상속 구조

특징:

• 단방향 관계
• 간선에 방향 존재
• 비대칭적 관계 표현

실제 사례:

• Twitter 팔로우: 내가 BTS 팔로우 ≠ BTS가 나를 팔로우
• 웹 하이퍼링크: A 페이지가 B로 링크 ≠ B가 A로 링크
• 상속 관계: 자식 클래스 → 부모 클래스

제가 트위터 클론 만들 때 이거 헷갈려서 버그 만든 적 있습니다. 무방향으로 설계했다가 "맞팔" 개념이 안 되더라고요.

가중치 그래프 (Weighted Graph)

   15km
A ───── B
│       │
10km    20km
│       │
C ───── D
   12km

간선에 비용/가중치 표시
예: 거리, 시간, 가격, 대역폭

특징:

• 간선마다 수치(비용) 존재
• 최단 경로가 "최소 비용 경로"
• 현실 세계의 제약 조건 반영

실제 사례:

• 내비게이션: 거리, 시간, 톨게이트 비용
• 항공편: 가격, 비행 시간, 환승 횟수
• 네트워크 라우팅: 대역폭, 지연시간(latency)

DAG (Directed Acyclic Graph)

A → B → D
↓   ↓
C ─→ E

방향 있고 + 사이클 없음

왜 중요한가:

• 의존성 관리의 핵심
• 순서가 있는 작업 표현
• 컴파일러, 빌드 시스템의 기반

실제 사례:

• npm/yarn 패키지 의존성: A가 B 의존, B가 C 의존
• 대학 선수과목: 자료구조 듣고 → 알고리즘 듣기
• Git commit 히스토리
• Webpack 모듈 번들링

제가 회사에서 빌드 시스템 만들 때 DAG를 활용했습니다. 모듈 의존성을 DAG로 표현하고, 위상 정렬(Topological Sort)로 빌드 순서를 결정했습니다.

이분 그래프 (Bipartite Graph)

학생   수업
A ─── Math
B ─── CS
C ─── Math
      Physics

두 그룹 사이 간선만 존재

특징:

• 정점이 두 그룹으로 나뉨
• 같은 그룹 내 간선 없음
• 매칭 문제에 유용

실제 사례:

• 채용 매칭: 지원자 ↔ 회사
• 수강 신청: 학생 ↔ 강의
• 추천 시스템: 사용자 ↔ 상품

3. 그래프 표현 - 인접 행렬 vs 인접 리스트

"어떻게 저장하지?"가 제일 중요한 질문이었습니다.

인접 행렬 (Adjacency Matrix)

2D 배열로 표현:

// 4명의 친구 관계
// 0: Alice, 1: Bob, 2: Charlie, 3: David
const matrix = [
  [0, 1, 1, 0],  // Alice: Bob, Charlie 친구
  [1, 0, 0, 1],  // Bob: Alice, David 친구
  [1, 0, 0, 0],  // Charlie: Alice만 친구
  [0, 1, 0, 0]   // David: Bob만 친구
];

// Alice(0)와 Bob(1) 친구인지 확인
if (matrix[0][1] === 1) {
  console.log("친구입니다!");  // O(1) 초고속!
}

// Alice의 모든 친구 찾기
const aliceFriends = [];
for (let i = 0; i < matrix[0].length; i++) {
  if (matrix[0][i] === 1) {
    aliceFriends.push(i);
  }
}
// O(V) 시간 - 모든 열을 확인해야 함

장점:

• 관계 확인: O(1) - 배열 인덱스 접근만 하면 됨
• 구현 단순: 2D 배열만 있으면 됨
• 간선 추가/삭제: O(1)
• Dense Graph (간선 많음)에 효율적

단점:

• 공간 복잡도: O(V²) - 정점 많으면 메모리 폭발
• 10,000명 → 100,000,000칸 필요 (대부분 0으로 낭비)
• 모든 이웃 찾기: O(V) - 전체 행을 스캔해야 함
• Sparse Graph (간선 적음)에 비효율적

언제 사용하나:

• 정점 수가 적을 때 (수백 개 이하)
• 간선이 매우 많을 때 (밀집 그래프)
• 관계 확인이 빈번할 때

제가 실수한 경험: SNS 프로토타입을 행렬로 만들었다가 사용자 1만 명만 돼도 메모리가 터져버렸습니다.

인접 리스트 (Adjacency List)

Map/Object로 표현:

// 같은 친구 관계를 리스트로
const list = {
  'Alice': ['Bob', 'Charlie'],
  'Bob': ['Alice', 'David'],
  'Charlie': ['Alice'],
  'David': ['Bob']
};

// Alice의 모든 친구 찾기
console.log(list['Alice']);  // O(1) - 즉시 접근!
// ['Bob', 'Charlie']

// Alice와 Bob 친구인지 확인
const isFriend = list['Alice'].includes('Bob');
// O(degree) - Alice의 친구 수만큼 검색

장점:

• 공간 복잡도: O(V + E) - 실제 관계만 저장
• 메모리 효율적: 100만 명 사용자도 문제없음
• 모든 이웃 찾기: O(1) - 리스트 반환만 하면 됨
• Sparse Graph (간선 적음)에 이상적

단점:

• 관계 확인: O(degree) - 리스트 순회 필요
• 구현 복잡도 약간 증가

언제 사용하나:

• 정점 수가 많을 때 (수천, 수만 개 이상)
• 간선이 적을 때 (희소 그래프) - 대부분의 실제 그래프
• 이웃 탐색이 주된 작업일 때

비교 테이블

항목	인접 행렬	인접 리스트
공간	O(V²)	O(V + E)
관계 확인	O(1)	O(degree)
이웃 찾기	O(V)	O(1)
간선 추가	O(1)	O(1)
간선 삭제	O(1)	O(degree)
적합한 경우	밀집 그래프, 작은 V	희소 그래프, 큰 V
실제 사용	게임 맵 (좁은 공간)	SNS, 웹 크롤링

결국 이해했습니다: 대부분의 현실 그래프는 희소 그래프라서 인접 리스트를 써야 한다.

4. BFS (너비 우선 탐색) - 최단 경로의 왕

문제 - 지하철 최소 환승

지하철역 A에서 E까지 최소 환승으로 가려면?

A ─ B ─ C
│       │
D ─ E ─ F

BFS로 해결

// BFS: 큐 기반, 레벨별 탐색
function shortestPath(graph, start, end) {
  // 큐 초기화: [현재 노드, 경로 배열]
  const queue = [[start, [start]]];
  const visited = new Set([start]);

  while (queue.length > 0) {
    // FIFO: 먼저 들어온 것부터 처리
    const [current, path] = queue.shift();

    // 목적지 도착!
    if (current === end) {
      return path;  // 첫 번째로 찾은 경로 = 최단 경로
    }

    // 모든 인접 노드 탐색
    graph[current].forEach(neighbor => {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        // 경로에 이웃 추가해서 큐에 넣기
        queue.push([neighbor, [...path, neighbor]]);
      }
    });
  }

  return null;  // 경로 없음
}

// 실제 사용
const subwayGraph = {
  'A': ['B', 'D'],
  'B': ['A', 'C'],
  'C': ['B', 'F'],
  'D': ['A', 'E'],
  'E': ['D', 'F'],
  'F': ['C', 'E']
};

const route = shortestPath(subwayGraph, 'A', 'E');
console.log(route);  // ['A', 'D', 'E'] - 2번 환승!

BFS가 최단 경로를 보장하는 이유

핵심 원리:

1. 레벨별로 탐색 (1단계 → 2단계 → 3단계...)
2. 가까운 노드부터 방문
3. 먼저 발견한 경로 = 최소 깊이 경로

시각화:

시작: A (레벨 0)
  ↓
레벨 1: B, D (A의 이웃)
  ↓
레벨 2: C, E (B, D의 이웃)
  ↓
E 발견! (레벨 2 = 거리 2)

시간/공간 복잡도

• 시간: O(V + E)
  • 모든 정점 방문: V
  • 모든 간선 확인: E
• 공간: O(V)
  • 큐, visited 세트

실제 활용 사례

제가 회사에서 만든 것들:

1. LinkedIn "2촌" 찾기

function findSecondDegree(graph, user) {
  const firstDegree = graph[user];  // 1촌
  const secondDegree = new Set();

  // BFS 2단계만 수행
  firstDegree.forEach(friend => {
    graph[friend].forEach(friendOfFriend => {
      // 나 자신 제외, 1촌 제외
      if (friendOfFriend !== user &&
          !firstDegree.includes(friendOfFriend)) {
        secondDegree.add(friendOfFriend);
      }
    });
  });

  return Array.from(secondDegree);
}

const result = findSecondDegree(network, 'Alice');
// "회원님이 알 수도 있는 사람"

2. 소셜 미디어 피드 확산

• 게시물이 몇 단계 떨어진 사람까지 퍼지는가?
• BFS로 레벨별 도달 범위 계산

3. 웹 크롤러

• 시작 URL에서 N단계 이내 페이지만 크롤링
• BFS로 깊이 제한

5. DFS (깊이 우선 탐색) - 경로 탐색과 사이클 감지

문제 - 순환 참조 버그

제가 회사에서 만난 실제 버그:

사용자 권한 시스템
AdminA → AdminB → AdminC → AdminA
↑___________________________|

무한 루프 발생! 서버 다운!

DFS로 사이클 감지

// DFS: 재귀 기반 (또는 스택 기반)
function hasCycle(graph, node, visited = new Set(), recStack = new Set()) {
  // 현재 경로에 이미 있으면 사이클!
  if (recStack.has(node)) {
    console.log(`사이클 감지: ${node}로 다시 돌아옴`);
    return true;
  }

  // 이미 완전히 탐색한 노드면 스킵
  if (visited.has(node)) {
    return false;
  }

  // 방문 표시
  visited.add(node);
  recStack.add(node);  // 현재 재귀 경로에 추가

  // 모든 인접 노드 깊이 우선 탐색
  for (const neighbor of graph[node]) {
    if (hasCycle(graph, neighbor, visited, recStack)) {
      return true;  // 사이클 발견 즉시 종료
    }
  }

  // 백트래킹: 현재 경로에서 제거
  recStack.delete(node);
  return false;
}

// 실제 사용: 권한 시스템 검증
const permissionGraph = {
  'AdminA': ['AdminB'],
  'AdminB': ['AdminC'],
  'AdminC': ['AdminA']  // 순환!
};

if (hasCycle(permissionGraph, 'AdminA')) {
  console.log("순환 참조 감지! 시스템 수정 필요");
}

DFS vs BFS 비교

DFS	BFS
스택/재귀	큐
깊이 우선 (끝까지)	너비 우선 (레벨별)
경로 탐색, 사이클 감지	최단 경로
메모리 적음 (O(H))	메모리 많음 (O(W))
백트래킹에 적합	최단 거리에 적합

DFS 활용

1. 미로 탈출 (백트래킹)

function solveMaze(maze, x, y, visited = new Set()) {
  // 목적지 도착
  if (isExit(x, y)) return true;

  // 방문 표시
  visited.add(`${x},${y}`);

  // 4방향 탐색 (상하좌우)
  for (const [dx, dy] of [[0,1], [0,-1], [1,0], [-1,0]]) {
    const nx = x + dx, ny = y + dy;
    if (isValid(nx, ny) && !visited.has(`${nx},${ny}`)) {
      if (solveMaze(maze, nx, ny, visited)) {
        return true;  // 경로 찾음!
      }
    }
  }

  // 백트래킹: 이 경로는 막다른 길
  return false;
}

2. npm 의존성 검증

• 패키지 A → B → C → A 순환 의존성 감지
• DFS로 설치 순서 결정

3. Git 커밋 히스토리 탐색

• 특정 브랜치에서 다른 브랜치로 가는 경로

6. 다익스트라 - 가중치 그래프의 최단 경로

BFS는 "최소 홉 수"를 찾지만, 다익스트라는 "최소 비용"을 찾습니다.

탐욕 알고리즘 (Greedy Approach)

핵심 아이디어:

1. 현재까지 알려진 최단 거리 유지
2. 매번 가장 가까운 미방문 노드 선택
3. 그 노드를 통한 경로로 거리 갱신

우선순위 큐 최적화

// 다익스트라: Priority Queue (최소 힙) 사용
function dijkstra(graph, start, end) {
  // 각 노드까지의 최단 거리
  const distances = { [start]: 0 };

  // 우선순위 큐 (거리 기준 오름차순)
  const pq = [{ node: start, dist: 0 }];
  const visited = new Set();

  while (pq.length > 0) {
    // 가장 가까운 노드 선택 (탐욕적 선택)
    pq.sort((a, b) => a.dist - b.dist);
    const { node, dist } = pq.shift();

    // 이미 방문했으면 스킵
    if (visited.has(node)) continue;
    visited.add(node);

    // 목적지 도착
    if (node === end) {
      return { distance: dist, path: reconstructPath(distances, start, end) };
    }

    // 인접 노드 거리 업데이트
    graph[node].forEach(({ to, weight }) => {
      const newDist = dist + weight;

      // 더 짧은 경로 발견시 갱신
      if (!distances[to] || newDist < distances[to]) {
        distances[to] = newDist;
        pq.push({ node: to, dist: newDist });
      }
    });
  }

  return null;  // 경로 없음
}

// 실제 사용: 내비게이션
const cityGraph = {
  'Seoul': [
    { to: 'Daejeon', weight: 140 },
    { to: 'Gangneung', weight: 165 }
  ],
  'Daejeon': [
    { to: 'Seoul', weight: 140 },
    { to: 'Daegu', weight: 120 }
  ],
  'Daegu': [
    { to: 'Daejeon', weight: 120 },
    { to: 'Busan', weight: 90 }
  ],
  'Gangneung': [
    { to: 'Seoul', weight: 165 }
  ],
  'Busan': [
    { to: 'Daegu', weight: 90 }
  ]
};

const result = dijkstra(cityGraph, 'Seoul', 'Busan');
// { distance: 350, path: ['Seoul', 'Daejeon', 'Daegu', 'Busan'] }

다익스트라의 한계

음수 가중치 불가:

• 탐욕적 선택이 실패함
• 이미 방문한 노드를 다시 확인 안 함
• 음수 가중치는 벨만-포드(Bellman-Ford) 알고리즘 사용

시간 복잡도:

• 우선순위 큐 미사용: O(V²)
• 이진 힙 사용: O((V + E) log V)
• 피보나치 힙 사용: O(E + V log V)

활용

제가 실제로 사용한 사례:

1. Google Maps / 카카오맵

• 거리, 시간, 톨게이트 비용 고려
• A* 알고리즘 (다익스트라 + 휴리스틱)

2. 네트워크 라우팅

• OSPF (Open Shortest Path First) 프로토콜
• 패킷이 최소 지연시간으로 목적지 도달

3. 게임 AI

• NPC가 플레이어에게 최단 경로로 접근

7. 위상 정렬 - 의존성 해결의 마스터

DAG의 선형 순서

위상 정렬은 "어떤 순서로 실행해야 하는가?"를 해결합니다.

// Kahn's 알고리즘: BFS 기반
function topologicalSort(graph) {
  // 1. 진입 차수(in-degree) 계산
  const inDegree = {};
  const result = [];

  // 모든 노드 초기화
  for (const node in graph) {
    inDegree[node] = 0;
  }

  // 진입 간선 개수 세기
  for (const node in graph) {
    graph[node].forEach(neighbor => {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    });
  }

  // 2. 진입 차수 0인 노드들 큐에 추가
  const queue = [];
  for (const node in inDegree) {
    if (inDegree[node] === 0) {
      queue.push(node);
    }
  }

  // 3. BFS로 순서 결정
  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);

    // 인접 노드의 진입 차수 감소
    graph[current]?.forEach(neighbor => {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    });
  }

  // 4. 사이클 검증
  if (result.length !== Object.keys(graph).length) {
    throw new Error("사이클 존재! DAG가 아님");
  }

  return result;
}

// 실제 사용: npm 패키지 설치 순서
const packageDeps = {
  'react': [],
  'react-dom': ['react'],
  'redux': [],
  'react-redux': ['react', 'redux'],
  'next': ['react', 'react-dom']
};

const installOrder = topologicalSort(packageDeps);
console.log(installOrder);
// ['react', 'redux', 'react-dom', 'react-redux', 'next']

활용

1. 빌드 시스템 (Make, Webpack)

TypeScript 컴파일 → Babel 트랜스파일 → 번들링 → 압축

2. 대학 선수과목

기초수학 → 선형대수 → 머신러닝
         → 미적분학 → 딥러닝

3. 작업 스케줄링

Task A 완료 → Task B, C 시작 가능

제가 회사에서 CI/CD 파이프라인 만들 때 위상 정렬로 빌드 단계 순서를 자동 결정했습니다.

8. 실제 - 추천 시스템 구현

제가 만든 "이 상품을 본 사람은..." 기능 전체 코드:

// 상품 구매 관계 그래프 (가중치 포함)
const purchaseGraph = {
  'smartphone': [
    { product: 'charger', weight: 0.8 },      // 80% 함께 구매
    { product: 'case', weight: 0.75 },
    { product: 'screen-protector', weight: 0.6 }
  ],
  'charger': [
    { product: 'smartphone', weight: 0.8 },
    { product: 'cable', weight: 0.5 }
  ],
  'case': [
    { product: 'smartphone', weight: 0.75 },
    { product: 'screen-protector', weight: 0.4 }
  ],
  'screen-protector': [
    { product: 'smartphone', weight: 0.6 },
    { product: 'case', weight: 0.4 }
  ],
  'cable': [
    { product: 'charger', weight: 0.5 }
  ]
};

// 스코어 기반 추천 (그래프 탐색 + 가중치)
function recommendProducts(currentCart, maxRecommendations = 5) {
  const scores = {};

  // 1. 장바구니 상품들의 관련 상품 점수 계산
  currentCart.forEach(item => {
    purchaseGraph[item]?.forEach(({ product, weight }) => {
      // 이미 장바구니에 있으면 제외
      if (!currentCart.includes(product)) {
        scores[product] = (scores[product] || 0) + weight;
      }
    });
  });

  // 2. 점수 높은 순으로 정렬
  const recommendations = Object.entries(scores)
    .sort(([, a], [, b]) => b - a)
    .slice(0, maxRecommendations)
    .map(([product, score]) => ({ product, score }));

  return recommendations;
}

// 실제 사용
const cart = ['smartphone'];
const recommendations = recommendProducts(cart);
console.log(recommendations);
// [
//   { product: 'charger', score: 0.8 },
//   { product: 'case', score: 0.75 },
//   { product: 'screen-protector', score: 0.6 }
// ]

// 여러 상품이 담긴 경우
const cart2 = ['smartphone', 'charger'];
const recommendations2 = recommendProducts(cart2);
// charger와 smartphone 둘 다 관련된 상품은 점수 합산

이 시스템으로 전환율(conversion rate)이 15% 상승했습니다. 그래프가 돈이 되더라고요.

9. 그래프 DB - Neo4j 실제

SQL JOIN 지옥을 벗어나 그래프 DB로 전환한 경험:

Cypher 쿼리 예시

// 1. 친구의 친구 찾기 (2촌)
MATCH (me:User {name: 'Alice'})-[:FRIEND]-(friend)-[:FRIEND]-(fof)
WHERE fof <> me AND NOT (me)-[:FRIEND]-(fof)
RETURN DISTINCT fof.name, COUNT(friend) AS mutualFriends
ORDER BY mutualFriends DESC
LIMIT 10;

// 2. 최단 경로 찾기
MATCH path = shortestPath(
  (a:User {name: 'Alice'})-[:FRIEND*]-(b:User {name: 'Bob'})
)
RETURN length(path) AS degrees, nodes(path) AS connections;

// 3. 상품 추천 (3단계 깊이)
MATCH (user:User {id: 123})-[:PURCHASED]->(p1:Product)
      -[:RELATED_TO]->(p2:Product)
      -[:RELATED_TO]->(p3:Product)
WHERE NOT (user)-[:PURCHASED]->(p3)
RETURN p3.name, p3.price, COUNT(*) AS relevance
ORDER BY relevance DESC
LIMIT 5;

// 4. 영향력 있는 사용자 찾기 (PageRank)
CALL gds.pageRank.stream('socialNetwork')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS user, score
ORDER BY score DESC
LIMIT 10;

// 5. 커뮤니티 감지 (Louvain 알고리즘)
CALL gds.louvain.stream('socialNetwork')
YIELD nodeId, communityId
RETURN communityId, COLLECT(gds.util.asNode(nodeId).name) AS members
ORDER BY SIZE(members) DESC;

SQL vs Cypher 비교

SQL (3촌 찾기):

SELECT DISTINCT u3.*
FROM users u1
JOIN friends f1 ON u1.id = f1.user_id
JOIN users u2 ON f1.friend_id = u2.id
JOIN friends f2 ON u2.id = f2.user_id
JOIN users u3 ON f2.friend_id = u3.id
JOIN friends f3 ON u3.id = f3.user_id
WHERE u1.id = 123
  AND u3.id NOT IN (
    SELECT friend_id FROM friends WHERE user_id = 123
  );
-- JOIN 지옥... 성능 끔찍함

Cypher (3촌 찾기):

MATCH (me:User {id: 123})-[:FRIEND*3]-(thirdDegree)
WHERE NOT (me)-[:FRIEND]-(thirdDegree)
RETURN DISTINCT thirdDegree;
-- 간결하고 빠름!

왜 그래프 DB를 선택했나

제가 느낀 장점:

• 관계 중심 쿼리가 100배 이상 빠름
• 스키마 변경 유연함
• 복잡한 관계 직관적으로 표현
• 실시간 추천 시스템에 최적

단점:

• 학습 곡선 있음 (Cypher 문법)
• 대용량 데이터 처리는 전통 DB가 나을 수도
• 백업/복구 도구 적음

결국 이해했습니다: 관계가 데이터보다 중요하면 그래프 DB.

10. 그래프 컬러링 - 스케줄링 문제

문제 - 시험 일정 짜기

학생들이 여러 과목 수강
같은 학생이 듣는 과목들은 다른 시간에 시험
최소 시험일로 일정 짜기

그래프 컬러링으로 해결

// 그리디 컬러링 알고리즘
function graphColoring(graph) {
  const colors = {};
  const nodes = Object.keys(graph);

  nodes.forEach(node => {
    // 인접 노드들이 사용한 색상
    const usedColors = new Set();
    graph[node].forEach(neighbor => {
      if (colors[neighbor] !== undefined) {
        usedColors.add(colors[neighbor]);
      }
    });

    // 사용 안 한 색상 중 가장 작은 번호
    let color = 0;
    while (usedColors.has(color)) {
      color++;
    }
    colors[node] = color;
  });

  return colors;
}

// 시험 일정: 겹치는 학생 있으면 간선
const examConflicts = {
  'Math': ['Physics', 'CS'],
  'Physics': ['Math', 'Chemistry'],
  'CS': ['Math', 'English'],
  'Chemistry': ['Physics'],
  'English': ['CS']
};

const schedule = graphColoring(examConflicts);
console.log(schedule);
// { Math: 0, Physics: 1, CS: 1, Chemistry: 0, English: 0 }
// 0일: Math, Chemistry, English
// 1일: Physics, CS
// → 2일이면 충분!

11. 실제 세계의 그래프들

제가 발견한 그래프들:

1. PageRank (Google 검색)

• 웹페이지 = 정점
• 링크 = 간선
• 많이 링크된 페이지 = 중요한 페이지
• 그래프 알고리즘이 구글을 만들었습니다

2. 소셜 네트워크 분석

• 영향력 측정 (중심성 알고리즘)
• 커뮤니티 탐지 (클러스터링)
• 정보 확산 시뮬레이션

3. A 알고리즘 (게임/내비게이션)*

• 다익스트라 + 휴리스틱
• 목표 방향 우선 탐색
• 스타크래프트 유닛 이동

4. 의존성 관리

• npm, yarn: 패키지 의존성 그래프
• Webpack: 모듈 번들링
• Maven, Gradle: 빌드 의존성

5. 네트워크 라우팅

• BGP (Border Gateway Protocol)
• 인터넷 전체가 거대한 그래프

마치며 - "모든 것은 연결되어 있다"

처음엔 "그래프가 뭐야? 차트?"라고 생각했습니다.

지금은 어디서든 그래프를 봅니다:

• 출근길 지하철 = 그래프 탐색
• LinkedIn 알림 = 2촌 BFS
• 유튜브 추천 = 그래프 기반 추천
• npm install = 위상 정렬
• Google 검색 = PageRank

"세상은 점(Node)과 선(Edge)로 이루어져 있다."

시니어가 했던 말이 이제야 와닿았습니다. 그래프는 단순한 자료구조가 아니라 세상을 보는 방식이었습니다. 모든 것은 연결되어 있고, 그 연결을 이해하는 게 문제 해결의 핵심이었습니다.

그래프를 공부하면서 가장 큰 깨달음: 복잡해 보이는 문제도 정점과 간선으로 단순화하면 해결책이 보인다.