그래프(Graph) 완벽 정리
그래프(Graph)는 여러 개의 노드(Node, 정점)들이 연결된 자료구조다.
트리가 부모-자식 관계로 연결된 계층적 구조였다면, 그래프는 좀 더 자유로운 연결 구조를 갖고 있다
즉, 어떤 데이터들이 서로 연결될 수 있는지 표현하는 강력한 자료구조.
✅ 그래프란?
그래프는 노드(Node, 정점) 들과 이들을 연결하는 간선(Edge) 들로 이루어진 자료구조이다.
각 노드는 여러 개의 다른 노드와 연결될 수 있으며, 연결의 방향과 유무에 따라 그래프의 종류가 달라진다.
쉽게 비유하면?
• 도시 지도 : 각 도시(노드)들이 도로(간선)로 연결된 모습
• SNS 친구 관계 : 유저(노드)들이 서로 친구 요청(간선)을 보내서 연결된 모습
그래프의 기본 용어
| 용어 | 설명 | 예시 |
|---|---|---|
| 노드(Node, 정점) | 그래프에서 하나의 개체(점) | 도시, SNS 사용자 |
| 간선(Edge) | 노드들을 연결하는 선 | 도로, 친구 관계 |
| 가중치(Weight) | 간선의 비용(거리, 시간 등) | 서울↔부산 거리 400km |
| 차수(Degree) | 한 노드에 연결된 간선 개수 | 한 사람이 가진 친구 수 |
노드(Node)와 간선(Edge)
A, B, C 세 개의 노드가 있다고 가정해보자.
A ↔ B, B ↔ C로 연결되어 있다면?
A - B - C (연결 상태)
여기서 A, B, C는 노드(Node), A-B, B-C는 간선(Edge)
그래프의 종류
그래프는 방향성과 가중치에 따라 여러 가지로 나뉜다.
1️⃣ 방향 그래프(Directed Graph) vs 무방향 그래프(Undirected Graph)
- 무방향 그래프 (Undirected Graph)
• 간선에 방향이 없음
• A ↔ B (A에서 B로 갈 수도 있고, B에서 A로도 갈 수 있음)
• 예시: SNS 친구 관계, 도로 양방향 통행
A - B - C여기서 A-B, B-C는 서로 양방향 연결이 가능
- 방향 그래프 (Directed Graph, Digraph)
• 간선에 방향이 있음 (한쪽으로만 이동 가능)
• A → B (A에서 B로 갈 수 있지만, B에서 A로 못 감)
• 예시: 트위터 팔로우, 도로 일방통행
A → B → CA에서 B로 갈 수 있지만, B에서 A로 돌아올 수 없음.
2️⃣ 가중치 그래프(Weighted Graph) vs 비가중치 그래프(Unweighted Graph)
- 비가중치 그래프
• 간선에 가중치가 없음 (연결 유무만 중요)
• 예시: SNS 친구 관계 (그냥 친구 여부만 중요)
- 가중치 그래프 (Weighted Graph)
• 간선에 비용이 있음 (거리, 시간 등)
• 예시: 지도에서 도시 간의 거리(서울↔부산 400km, 서울↔대전 140km)
A --(4)--> B --(2)--> C여기서 A→B 가중치는 4, B→C 가중치는 2
그래프의 표현 방법
그래프를 코드로 표현하는 방법은 여러 가지가 있다
주로 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 두 가지 방식이 많이 쓰인다.
1️⃣ 인접 행렬 (Adjacency Matrix)
• 그래프를 2차원 배열로 표현
• 노드 개수 n이면, n×n 행렬(배열)을 사용
• 공간 복잡도: O(n²) (노드 개수가 많으면 메모리 낭비 심함)
• 탐색 속도 빠름 (O(1))
// 3개의 노드(A, B, C)
const graph = [
[0, 1, 0], // A → B
[1, 0, 1], // B → A, B → C
[0, 1, 0] // C → B
];
console.log(graph[0][1]); // 1 (A→B 연결됨)
console.log(graph[0][2]); // 0 (A→C 연결 안 됨)행렬에서 1이면 연결됨, 0이면 연결되지 않음
2️⃣ 인접 리스트 (Adjacency List)
• 노드별로 연결된 노드 리스트를 저장
• 공간 효율적 (O(V + E), 노드+간선 개수만큼)
• 탐색 속도는 다소 느릴 수 있음 (O(V))
const graph = {
A: ["B"],
B: ["A", "C"],
C: ["B"]
};
console.log(graph["A"]); // ['B'] (A는 B와 연결됨)
console.log(graph["B"]); // ['A', 'C'] (B는 A, C와 연결됨)각 노드별로 연결된 노드를 리스트로 저장하는 방식
그래프 탐색 (Graph Traversal)
그래프에서 모든 노드 방문하기 위해 DFS와 BFS 탐색 방법이 사용됨
1️⃣ DFS (깊이 우선 탐색, Depth First Search)
• 한 갈래를 끝까지 탐색한 후 돌아오는 방식
• 재귀(Recursive) 또는 스택(Stack) 사용
• 주로 경로 찾기 문제에 사용
const graph = {
A: ["B", "C"],
B: ["A", "D", "E"],
C: ["A", "F"],
D: ["B"],
E: ["B", "F"],
F: ["C", "E"]
};
function dfs(node, visited = new Set()) {
if (visited.has(node)) return;
console.log(node); // 방문 출력
visited.add(node);
for (let neighbor of graph[node]) {
dfs(neighbor, visited);
}
}
dfs("A"); // A → B → D → E → F → C2️⃣ BFS (너비 우선 탐색, Breadth First Search)
• 같은 레벨의 노드들을 먼저 탐색
• 큐(Queue) 사용
• 최단 경로 문제에 자주 사용
function bfs(start) {
let queue = [start];
let visited = new Set();
while (queue.length > 0) {
let node = queue.shift();
if (visited.has(node)) continue;
console.log(node); // 방문 출력
visited.add(node);
for (let neighbor of graph[node]) {
queue.push(neighbor);
}
}
}
bfs("A"); // A → B → C → D → E → FBFS는 큐(Queue)를 이용해 같은 레벨 노드를 먼저 방문한다.
최단 경로 문제(미로 찾기, 지도 길 찾기)에 자주 사용됨
그래프 활용 예제
✔ 네트워크 연결: 컴퓨터 네트워크, 친구 관계, 추천 시스템
✔ SNS 관계 분석: 페이스북, 인스타그램의 친구 추천
✔ 지도 및 길 찾기: 네비게이션, 지하철 노선도
✔ 웹 크롤링: 페이지 간의 링크 구조 분석
✔ AI & 경로 탐색: 최적 경로 찾기 (A* 알고리즘)
마무리
✅ 그래프는 노드(Node)와 간선(Edge)로 이루어진 자료구조
✅ 방향 그래프 / 무방향 그래프, 가중치 그래프 / 비가중치 그래프가 있음
✅ 그래프 표현 방식: 인접 행렬 vs 인접 리스트
✅ 탐색 방법: DFS(깊이 우선 탐색), BFS(너비 우선 탐색)
✅ 실생활에서 다양한 문제 해결에 사용됨
