📅 2025-11-04
➡️ 그래프 알고리즘에 대해 새롭게 알게 된 것 또는 헷갈리는 부분 정리
🔎 학습 리마인드
📌 그래프 (Graph)
💡 그래프 기본 개념
- 정점(Vertex, Node): 데이터가 놓이는 점
- 간선(Edge): 정점-정점 연결
- 가중치(Weight): 간선의 비용/거리
- 방향 그래프(Directed) / 무방향 그래프(Undirected)
- 인접(Adjacent): 간선으로 직접 연결된 관계
- 차수(Degree): 정점에 연결된 간선 수 (유향은 in-degree/out-degree)
- 사이클(Cycle): 시작 정점으로 돌아오는 닫힌 경로
- 연결 요소(Connected Component): 서로 도달 가능한 정점들의 묶음
💡 트리 vs. 그래프
-
트리
- 루트 1개
- 부모-자식
- 사이클 없음
- 간선 수 = 정점 수 - 1
-
그래프
- 루트 개념 없음
- 사이클 있을 수 있음
- 간선 수 제한 없음
📌 그래프 종류
💡 방향 그래프 (Directed Graph)
- 간선(Edge) 방향이 존재
- 하나 이상의 사이클이 있는 그래프 → 사이클 그래프 (Cyclic Graph)
- 사이클이 하나도 없는 그래프 → 비사이클 그래프 (Acyclic Graph)
💡 무방향 그래프 (Undirected Graph)
- 간선 방향이 없음
📌 그래프 표현 방법
💡 인접 행렬 (Adjacency Matrix)
- 그래프를 2차원 배열(행렬) 형태로 표현하는 방식
- 노드 간의 연결 여부를 0과 1로 표시
const graphMatrix = [
[0, 1, 1, 1], // 1 -> 2, 3, 4
[1, 0, 0, 0], // 2 -> 1
[1, 0, 0, 1], // 3 -> 4
[1, 0, 1, 0], // 4 -> X
];💡 인접 리스트 (Adjacency List)
- 각 정점에 연결된 정점들을 리스트 형태로 저장
- 각 정점이 어떤 정점들과 연결되어 있는지를 리스트(배열, 객체, Map 등)로 표현하는 방식
const graphList = {
1: [2, 3, 4],
2: [1],
3: [1, 4],
4: [1, 2],
};📌 그래프 탐색
💡 DFS (깊이 우선 탐색, Depth First Search)
- 가능한 한 경로를 끝까지 따라간 다음, 막히면 이전 분기점으로 돌아가서 다시 탐색
- 스택(Stack) 자료구조를 사용하거나, 재귀 함수로 구현 가능
- 예) inOreder, preOrder, postOrder
탐색 순서 예시
- DFS 순서 A - B - E - D - H - G - C - F
DFS 코드
const graph = {
A: ["B"],
B: ["A", "E", "D", "C"],
E: ["B", "D"], // E 다음은 D
D: ["H", "G", "C", "E", "B"], // D에서 H → G → C 순으로
H: ["D"],
G: ["D"],
C: ["F", "D", "B"], // C 에서 F를 먼저
F: ["C"],
};// DFS (깊이 우선 탐색) 반복문 기반 -> 스택 사용
function dfs(graph, start) {
const visited = new Set(); // 이미 방문한 노드 저장
const stack = [start]; // 탐색할 노드를 저장하는 스택 (LIFO)
while (stack.length) {
const node = stack.pop(); // 스택의 마지막 노드를 꺼냄
if (!visited.has(node)) {
// 아직 방문 하지 않았을 때
console.log(node); // 방문 출력
visited.add(node); // 방문 표시
// 다음 방문할 인접 노드를 추가
for (const neighbor of graph[node].slice().reverse()) {
if (!visited.has(neighbor)) stack.push(neighbor);
}
}
}
}
// DFS 깊이 우선 탐색 (재귀 기반)
function dfsR(graph, node, visited = new Set()) {
visited.add(node);
console.log(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) dfsR(graph, neighbor, visited);
}
}graph[node].slice().reverse()를 쓰는 이유- 스택은 LIFO이기 때문에 그래프에 정의된 이웃 순서대로 방문하려면 이웃들을 역순으로 스택에 넣어야 함
Array.prototype.reverse()는 원본 배열을 직접 변경하기 때문에graph[node].slice()로 복사본을 만들어 주고, 그 복사본에reverse()를 적용하여 원본 유지
특징
- 한 갈래를 끝까지 탐색
- 경로 추적, 백트래킹 문제에 자주 사용 (예 : 순열/조합탐색, 연결 요소 탐색, 미로찾기)
💡 BFS (넓이 우선 탐색, Breath First Search)
- 시작 정점으로부터 가까운 정점부터 탐색
- 큐(Queue)를 자료구조로 사용
- 최단거리 탐색
- BFS 순서 A - B - C - D - E - F - G - H
BFS 코드
const graph = {
A: ["B"],
B: ["A", "C", "D", "E"],
C: ["B", "D", "F"],
D: ["C", "E", "G", "H"],
E: ["B", "D"],
F: ["C"],
G: ["D"],
H: ["D"],
};function bfs(graph, start) {
const visited = new Set(); // 방문한 노드 기록
const queue = [start]; // 다음에 방문할 노드를 담는 큐 (FIFO)
while (queue.length) {
const node = queue.shift(); // 큐의 맨 앞 요소를 꺼냄
if (!visited.has(node)) {
// 아직 방문하지 않았다면
console.log(node); // 방문 출력 (탐색 순서 확인용)
visited.add(node); // 방문 표시
// 인접 노드들을 순회
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) queue.push(neighbor); // 방문 예정 목록(큐)에 추가
}
}
}
}
bfs(graph, "A");특징
- 가까운 정점부터 탐색
- 항상 최단 경로를 보장
- 큐를 사용하여 반복문 구현에 적합
- 네트워크 최단거리 친구 추천 등 그래프 기반 탐색에 자주 사용
💡 DFS vs. BFS 비교
| 항목 | DFS | BFS |
|---|---|---|
| 방식 | 깊이 우선 | 너비 우선 |
| 구조 | 스택(재귀) | 큐 |
| 장점 | 구현이 간단, 백트래킹에 유리 | 최단 경로 탐색에 유리 |
| 단점 | 최단 경로 보장 안됨 | 구현 복잡, 메모리 많이 사용 |
| 실전 예시 | 미로 찾기, 백트래킹 문제 | 게임 맵 탐색, 네트워크 탐색 |
🌊 Deep Dive
🤔 인접 리스트 기반 그래프 + DFS/BFS 탐색 구현
class Node {
constructor(data) {
this.data = data; // 실제 데이터
this.marked = false; // 방문 마킹
this.adjacent = []; // 인접한 노드
}
}
class Graph {
constructor() {
this.nodes = [];
}
add(data) {
const node = new Node(data);
this.nodes.push(node);
return node;
}
addEdge(node1, node2) {
//넣기 전에 인접한 노드
if (!node1.adjacent.includes(node2)) {
node1.adjacent.push(node2); // node1 -> node2
}
if (!node2.adjacent.includes(node1)) {
node2.adjacent.push(node1); // node2 -> node1
}
}
dfs(start) {
const visited = new Set();
const stack = [start];
while (stack.length) {
const node = stack.pop();
if (!visited.has(node)) {
console.log(node.data);
visited.add(node);
for (let neighbor of node.adjacent) {
if (!visited.has(neighbor)) stack.push(neighbor);
}
}
}
}
bfs(start) {
const visited = new Set();
const queue = [start];
while (queue.length) {
const node = queue.shift();
if (!visited.has(node)) {
console.log(node.data);
visited.add(node);
for (let neighbor of node.adjacent) {
if (!visited.has(neighbor)) queue.push(neighbor);
}
}
}
}
}
const graph = new Graph();
const A = graph.add('A');
const B = graph.add('B');
const C = graph.add('C');
const D = graph.add('D');
const E = graph.add('E');
const F = graph.add('F');
const G = graph.add('G');
const H = graph.add('H');
graph.addEdge(A, B);
graph.addEdge(A, C);
graph.addEdge(B, D);
graph.addEdge(B, E);
graph.addEdge(C, F);
graph.addEdge(D, G);
graph.addEdge(E, H);
/*
A
/ \
B C
/ \ \
D E F
| |
G H
*/
console.log(graph);
console.log('DFS 탐색 순서:');
graph.dfs(A);
console.log('BFS 탐색 순서:');
graph.bfs(A);- DFS : 스택을 사용해서 깊게 파고드는 방식
- BFS : 큐를 사용해서 넓게 한 레벨씩 탐색하는 방식
