(5) Graph

카카오 맵이 막히는 길을 피해 최적의 경로를 찾아주고, 유튜브가 내가 좋아할 것 같은 영상을 귀신같이 추천해주는 이유는 

Graph라는 자료구조 덕분이다. 우리가 매일 쓰는 앱들 뒤에 조용히 숨어서 열심히 일하고 있는 Graph라는 자료구조를 공부해보려고 한다.

 

---

Graph 란?

그래프는 노드(Node), 엣지(Edge)로 이뤄진 자료구조이다.

노드는 데이터를 담는 점이고, 엣지는 그 점들을 잇는 선이다.

친구 관계로 생각하면 사람 한 명 한 명이 노드고, "친구"라는 관계가 엣지인 것이다.

[나] ---- [친구A]
   |            |
[친구B] ---- [친구C]

트리도 사실 그래프의 일종이다. 다만 트리는 계층 구조가 있고 사이클이 없는 특수 형태의 그래프이다.

그래프는 트리보다 훨씬 자유로운 형태로 연결될 수 있다.

 

Graph의 종류 - 방향/무방향, 가중치, 순환/비순환, 연결/비연결, 완전 

그래프는 엣지의 성질에 따라 크게 나뉜다.

 

(1) 방향  VS 무방향 

무방향 그래프는 엣지에 방향이 없다. A-B로 연결되어 있으면 A -> B도 되고 B -> A 도 된다.

예를 들어 카카오톡 친구 관계가 이와 같다.

하지만 방향 그래프는 엣지에 방향이 있다. A -> B 는 가능하지만 B -> A는 안 될 수 있다.

마치 인스타그램 팔로우 처럼 말이다. 내가 누군가를 팔로우한다고 상대방이 무조건 나를 팔로우하는건 아닌것처럼!

무방향:  A ---- B      방향:  A ----> B

 

(2) 가중치 그래프

엣지에 숫자 (비용,거리,시간 등) 가 붙어있는 그래프이다. 지도에서 도시 간 거리나 이동 시간을 표현할때 쓰인다.

[서울] --100km-- [대전] --80km-- [대구]

 

(3) 순환 VS 비순환 

출발점으로 다시 돌아오는 경로 (사이클)가 있으면 순환 그래프, 없으면 비순환 그래프이다.

 

(4) 연결 VS 비연결

연결 그래프는 모든 노드가 최소 하나의 경로로 이어져있는 그래프이다.

어떤 노드에서 출발해도 다른 모든 노드에 도달 할 수 있다. 

비연결 그래프는 일부 노드가 완전히 끊겨있는 그래프이다. 섬 처럼 따로 떠있는 노드나 그룹이 존재하는 것이다.

연결 그래프          비연결 그래프
A - B - C           A - B     C - D
    |                         (C,D는 A,B와 단절)
    D

 

(5) 완전 그래프

모든 노드가 서로 직접 연결된 그래프이다. 노드가 N개면 엣지가 N(N-1) / 2 개가 된다.

노드 4개짜리 완전 그래프
A --- B
|\ /|
| X |
|/ \|
C --- D
(모든 노드가 서로 연결)

노드가 늘어날수록 엣지 수가 폭발적으로 증가하기 때문에 현실에선 잘 안 쓰이지만, 알고리즘 복잡도 분석이나 이론적인 기준점으로 자주 언급된다.

 

분류 기준종류

분류 기준	종류
방향성	방향 그래프 / 무방향 그래프
가중치	가중치 그래프 / 비가중치 그래프
사이클	순환 그래프 / 비순환 그래프
연결성	연결 그래프 / 비연결 그래프
밀도	완전 그래프 / 희소 그래프

 

---

Graph를 Javascript 코드로 표현하는 2가지 방법

(1) 인접 행렬 (Adjacency Matrix)

"인접" 이란 서로 연결되어 있다는 뜻이고 " 행렬"은 숫자를 표 형태로 나열한 것이다. 

합치면 연결 관계를 표로 나타낸 것 인데 그래프에서 노드끼리 연결됐는지 안됐는지를 0 과 1 로 표에 기록하는 방식이다.

연결 됐으면 1, 아니면 0으로 기록하면 된다.

 

예시를 들어 설명하면 다음과 같다. 

예를 들어 카카오맵에 도시 4개가 있다. 

서울 --- 대전 --- 대구 --- 부산
  \________________________/
         (직통 노선)

 

• 서울 ↔ 대전 연결 
• 대전 ↔ 대구 연결 
• 대구 ↔ 부산 연결 
• 서울 ↔ 부산 직통 연결

각 도시의 연결관계가 위와 같다고 설정하고 다음으로 빈표를 만든다.

도시가 4개니까 4X4 표를 만들고 처음엔 전부 0으로 해둔다.

서울(0)  대전(1)  대구(2)  부산(3)
서울(0) [  0,      0,      0,      0  ]
대전(1) [  0,      0,      0,      0  ]
대구(2) [  0,      0,      0,      0  ]
부산(3) [  0,      0,      0,      0  ]

 

그리고 연결된 곳에 1을 채운다.

서울(0) ↔ 대전(1) 연결 → [0][1] 과 [1][0] 에 1

대전(1) ↔ 대구(2) 연결 → [1][2] 과 [2][1] 에 1

대구(2) ↔ 부산(3) 연결 → [2][3] 과 [3][2] 에 1

서울(0) ↔ 부산(3) 직통 → [0][3] 과 [3][0] 에 1

서울(0)  대전(1)  대구(2)  부산(3)
서울(0) [  0,      1,      0,      1  ]
대전(1) [  1,      0,      1,      0  ]
대구(2) [  0,      1,      0,      1  ]
부산(3) [  1,      0,      1,      0  ]

 

그럼 위와 같이 표가 채워지게 되는데 대각선이 전부 0 인 이유는 자기 자신으로 가는 길은 없기 때문이다.

그리고 표가 대각선 기준으로 대칭인 이유는 서울 -> 대전이 연결됐다는 것은 대전 -> 서울도 되는 무방향 그래프이기 때문이다.

 

따라서 코드로 표현하게 되면 

const matrix = [
//   서울  대전  대구  부산
    [ 0,   1,   0,   1 ],  // 서울
    [ 1,   0,   1,   0 ],  // 대전
    [ 0,   1,   0,   1 ],  // 대구
    [ 1,   0,   1,   0 ],  // 부산
];

// "서울에서 대전 갈 수 있어?"
console.log(matrix[0][1]); // 1 → 갈 수 있다 

// "서울에서 대구 바로 갈 수 있어?"
console.log(matrix[0][2]); // 0 → 직통 없음 

// "서울에서 부산 직통 있어?"
console.log(matrix[0][3]); // 1 → 직통 있다 

// "서울에서 갈 수 있는 도시 전부 보여줘"
matrix[0].forEach((connected, city) => {
    if (connected === 1) {
        console.log(`서울 → ${city}번 도시 연결됨`);
    }
});
// 결과 : 서울 → 1번 도시 연결됨 (대전)
// 결과 : 서울 → 3번 도시 연결됨 (부산)

 

정리하자면 인접 행렬은 결국 "어느 도시끼리 연결됐는지를 표에 기록해두는 것" 이다.

연결됐으면 1, 아니면 0. 나중에 BFS/DFS나 최단경로 알고리즘을 배울 때, 이 표를 읽으면서 "다음에 어디로 갈 수 있지?" 를 확인하는 용도로 쓰이게 된다. 

 

(2) 인접 리스트 (Adjacency List)

인접 행렬이 "표"로 연결 관계를 저장했다면, 인접 리스트는 "각 도시마다 갈 수 있는 도시 목록을 따로 저장" 하는 방식이다.

위의 인접 행렬에서 쓴 상황을 다시 한번 대입해보자 

각 도시마다 연결된 도시들을 따로 리스트에 적는다. 

서울 → [대전, 부산]        (서울에서 갈 수 있는 곳)
대전 → [서울, 대구]        (대전에서 갈 수 있는 곳)
대구 → [대전, 부산]        (대구에서 갈 수 있는 곳)
부산 → [대구, 서울]        (부산에서 갈 수 있는 곳)

끝이다! 이게 바로 인접 리스트이다.

이를 코드로 표현하게 되면 아래와 같다.

const graph = {
    "서울": ["대전", "부산"],
    "대전": ["서울", "대구"],
    "대구": ["대전", "부산"],
    "부산": ["대구", "서울"],
};

// "서울에서 갈 수 있는 도시가 어디야?"
console.log(graph["서울"]); // ["대전", "부산"]

// "서울에서 대전 갈 수 있어?"
console.log(graph["서울"].includes("대전")); // true 

// "서울에서 대구 바로 갈 수 있어?"
console.log(graph["서울"].includes("대구")); // false 

// "서울에서 갈 수 있는 도시 전부 보여줘"
graph["서울"].forEach(city => {
    console.log(`서울 → ${city} 연결됨`);
});
// 서울 → 대전 연결됨
// 서울 → 부산 연결됨
```

---

### 인접 행렬 vs 인접 리스트 비교

```
인접 행렬                     인접 리스트
        서울 대전 대구 부산       서울 → [대전, 부산]
서울  [  0,  1,  0,  1 ]       대전 → [서울, 대구]
대전  [  1,  0,  1,  0 ]       대구 → [대전, 부산]
대구  [  0,  1,  0,  1 ]       부산 → [대구, 서울]
부산  [  1,  0,  1,  0 ]

 

 

인접 행렬은 연결 안된 곳도 전부 0으로 채워야 한다. 반면 인접 리스트는 실제로 연결된 것만 저장하니 훨신 가볍다.

도시가 1000개인데 연결은 몇 개 없다면? 인접 행렬은 1000×1000 = 100만 칸을 전부 만들어야 하지만, 인접 리스트는 연결된 것만 딱 저장하면 된다.

 

인접 행렬 vs 인접 리스트 비교

	인접 행렬	인접 리스트
공간 복잡도	O(V²)	O(V+E)
연결 확인	O(1)	O(V)
언제 쓸까?	노드가 적고 연결이 많을 때	대부분의 경우

 

공간 복잡도

인접 행렬 O(V²)

도시(노드)가 V개면 V×V 표를 만들어야 한다.

도시가 4개면 4×4=16칸, 100개면 100×100=10,000칸을 무조건 만들어야 한다.

빈칸을 전부 0으로 채워야 하니까 낭비가 심하다.

 

인접 리스트 O(V+E)

노드(V)마다 목록을 하나씩 만들고, 실제 연결된 간선(E)만 저장한다.

연결이 적으면 적게, 많으면 많이 저장하니까 훨씬 효율적이다.

 

연결 확인

인접 행렬 O(1)

matrix[0][3] 처럼 행과 열 번호만 알면 바로 꺼낼 수 있다. 몇 개가 있든 딱 한 번만 확인하면 끝이다.

 

인접 리스트 O(V)

graph["서울"].includes("부산") 처럼 리스트를 처음부터 끝까지 훑어야 한다. 최악의 경우 리스트에 모든 노드가 들어있을 수 있어서 V번 확인해야 할 수도 있다.

 

언제 쓸까?

인접 행렬 → 노드 수가 적고, 연결이 빽빽할 때 (완전 그래프에 가까울 때) 쓴다.

연결 확인을 엄청 자주 해야 하는 상황이라면 O(1)의 속도가 빛을 발한다.

 

인접 리스트 → 노드가 많고 연결이 듬성듬성할 때 쓴다. 현실의 그래프 대부분이 이 경우이다.

카카오맵만 해도 도시는 수천 개지만 직접 연결된 도로는 일부에 불과하기 때문이다. 

 

실전에서 그래프가 쓰이는 곳

(1) 길찾기 

도시가 노드, 도로가 엣지, 거리나 시간이 가중치이다.

[서울] --1시간-- [대전] --50분-- [대구] --1시간-- [부산]

"서울에서 부산까지 가장 빠른 길은?" 을 다익스트라 알고리즘 으로 푼다.

막히는 도로를 피하는 것도 실시간으로 가중치를 업데이트해서 최단 경로를 다시 계산하는 것이다.

 

(2) SNS 친구 추천

사람이 노드, 팔로우/친구 관계가 엣지 이다.

나 → A → B
나 → C → B

 

나와 직접 연결은 안 됐지만 A, C를 통해 B와 2번만에 닿는다.

이런 사람을 "알 수도 있는 친구"로 추천해준다. BFS로 2단계 떨어진 노드를 찾으면 되는 것이다.

 

(3) 배달 최적화

물류 센터와 배달지가 노드, 이동 경로가 엣지이다.

[물류센터] → [A아파트] → [B빌라] → [C오피스텔]

여러 배달지를 한 번에 돌 때 가장 효율적인 순서를 그래프로 계산한다.

기사님이 최소 거리로 모든 곳을 들를 수 있도록 경로를 최적화해주는 것이다.

이런 상황을 TSP (외판원 문제)  라고 하는데 모든 노드를 한 번씩 방문하는 가장 짧은 경로를 찾아요. 내부적으로 DFS나 동적 프로그래밍을 활용한다.

 

세 가지 예시에서 다익스트라, BFS, DFS, 동적 프로그래밍 같은 알고리즘들이 등장했는데, 이 알고리즘들은 전부 그래프를 기반으로 동작한다.

각 알고리즘의 개념과 구현은 다음 포스팅에서 하나씩 자세히 다뤄볼 예정이다.

 

---

그래프는 노드(Node) 와 엣지(Edge) 로 이루어진 자료구조이다.

방향/무방향, 가중치, 순환/비순환, 연결/비연결, 완전 그래프까지 다양한 종류가 있고,

표현 방법은 인접 행렬과 인접 리스트 두 가지가 있다.

인접 행렬은 연결 관계를 표로 저장해서 확인이 빠르지만 메모리 낭비가 있고,

인접 리스트는 연결된 것만 저장해서 효율적이다.. 그래서 실전에서는 대부분 인접 리스트를 쓴다.

그리고 이 그래프는 단순한 이론이 아니라 카카오맵 길찾기, 인스타그램 친구 추천, 쿠팡 배달 최적화처럼 우리가 매일 쓰는 서비스 속에 이미 존재하기 때문에 꼭 알아야하는 자료구조 중 하나라고 생각한다.