지금까지 배운 모든 자료구조(배열, 연결 리스트, 큐, 트리 등)가 데이터의 "상하/전후" 관계를 나타냈다면, 그래프(Graph)는 세상의 모든 "복잡한 네트워크(거미줄)" 관계를 표현할 수 있는 끝판왕 비선형 자료구조입니다.
우리가 매일 사용하는 지도 앱(카카오맵, 네비게이션)의 최단 경로 탐색, 인스타그램/페이스북의 친구 추천 시스템, 심지어 인공지능 신경망(Neural Network)까지 모두 그래프 자료구조를 기반으로 동작합니다.
1. 그래프의 구성 요소와 네트워크 모델
2. 인접 행렬(Matrix) vs 인접 리스트(List)
비교 항목
인접 행렬 (Adjacency Matrix)
인접 리스트 (Adjacency List)
구현 방식
2차원 배열(N x N)로 연결 여부를 0과 1로 표시
각 정점마다 배열/리스트를 두어 연결된 노드만 저장
메모리 공간
O(V²) (연결되지 않은 곳도 모두 저장하여 낭비 심함)
O(V + E) (실제 연결된 선의 개수만큼만 메모리 차지)
조회 속도
두 노드가 연결되었는지 확인 속도 매우 빠름 O(1)
해당 노드의 리스트를 순회해야 하므로 O(간선 수)
주 사용처
노드 개수가 적고 간선이 매우 빽빽한(Dense) 그래프
실무 대부분 (수백만 유저 SNS 등 듬성듬성한 Sparse 그래프)
💡 실무 지식: 그래프 탐색의 양대 산맥, BFS와 DFS
수많은 데이터가 복잡하게 얽힌 그래프에서 목적지를 찾는 두 가지 핵심 알고리즘이 있습니다. 1. BFS (너비 우선 탐색) : "나와 가까운 1촌부터 전부 스캔하고, 그 다음 2촌을 스캔하는 방식". 주로 최단 경로(네비게이션)를 찾을 때 사용하며 큐(Queue)를 사용해 구현합니다. 2. DFS (깊이 우선 탐색) : "한 우물만 끝까지 파고들어 갔다가, 막히면 되돌아오는 방식". 주로 모든 경로를 다 탐색(미로 찾기)해야 할 때 사용하며 재귀 함수나 스택(Stack)을 사용해 구현합니다.
// 📂 Graph.js (JavaScript)
// 그래프는 보통 인접 리스트(Adjacency List) 방식으로 구현합니다. (메모리 절약)
class Graph {
constructor() {
this.adjacencyList = {};
}
// 정점(Vertex) 추가
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
// 간선(Edge) 추가 (무방향 그래프 기준)
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1); // 양방향 연결
}
// 간선(Edge) 제거
removeEdge(v1, v2) {
this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
}
// 정점(Vertex) 제거
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
}
}
// 🌐 소셜 네트워크(SNS) 친구 관계 그래프 생성
const sns = new Graph();
sns.addVertex("Alice");
sns.addVertex("Bob");
sns.addVertex("Charlie");
sns.addEdge("Alice", "Bob"); // 앨리스와 밥은 친구!
sns.addEdge("Bob", "Charlie"); // 밥과 찰리는 친구!
console.log(sns.adjacencyList);
/*
출력 결과:
{
Alice: [ 'Bob' ],
Bob: [ 'Alice', 'Charlie' ],
Charlie: [ 'Bob' ]
}
*/
