대표적인 그래프 탐색 알고리즘
📌 차이점
📌 공통점
-
일반적인 BFS, DFS 시간 복잡도
-
노드 수: V
-
간선 수: E
-
시간 복잡도: O(V + E)
-
📌 구현 원리
🔹 BFS
- 그림으로 보기
STEP 1: A노드 부터 탐색을 시작할 것. 
STEP 2: A노드를 Visited 리스트에 넣음. A노드에 인접한 B, C를 큐에 넣음. 
STEP 3: 큐의 맨 앞에 있는 B를 Visited 리스트에 넣음. B에 인접한 노드 D를 큐에 넣음. 
STEP 4: 큐의 맨 앞에 있는 C를 Visited 리스트에 넣음. C에 인접한 노드 F를 큐에 넣음. 
STEP 5: 큐의 맨 앞에 있는 D를 Visited 리스트에 넣음. D에 인접한 F는 이미 큐에 있으므로 넘어감. 
STEP 6: 큐의 맨 앞에 있는 F를 Visited 리스트에 넣음. 큐는 비어있게 되므로 탐색을 종료.
🔹 DFS
- Step 1: 스택에 시작 노드를 넣음.
- Step 2: 스택이 비어있으면 실행을 멈추고 False 반환.
- Step 3: 스택의 맨 위 노드가 찾고자 하는 노드라면 탐색을 종료하고 True 반환.
- Step 4: Step 3에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를
POP함. 스택에 들어온 적이 없는POP한 노드의 모든 이웃 노드를 찾아서 순서대로 스택에 넣음.- Step 5: Step 3로 돌아감.
- 그림으로 보기
STEP 1: A를 시작노드로 함. 
STEP 2: A에 인접한 B, C가 스택에 저장됨. 
STEP 3: 스택의 맨 위에 있는 C를 꺼내서 Visited 배열에 넣음. C의 인접한 노드인 D, F가 스택에 저장됨. 
STEP 4: 스택의 맨 위에 있는 F를 꺼내서 Visited 배열에 넣음. F에 인접한 노드인 D는 이미 Stack에 있으므로 넘어감. 
STEP 5: 스택의 맨 위에 있는 D를 꺼내서 Visited 배열에 넣음. D에 인접한 C, F는 Visited 배열에 있으며 B는 스택에 있으므로 넘어감. 
STEP 6: 스택의 맨 위에 있는 B를 꺼내서 Visited 배열에 넣음. 스택이 비어있으므로 탐색을 종료함.
📌 예제
- BFS 방식: A - B - C - D - G - H - I - E - F - J
- DFS 방식: A - B - D - E - F - C - G - H - I - J
🔹 코드
// 1️⃣ [자바스크립트로 그래프 표현하기]
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'G', 'H', 'I'],
D: ['B', 'E', 'F'],
E: ['D'],
F: ['D'],
G: ['C'],
H: ['C'],
I: ['C', 'J'],
J: ['I']
};
// 2️⃣ [BFS 구현]
const BFS = (graph, startNode) => {
const visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...needVisit, ...graph[node]];
}
}
return visited;
};
console.log(BFS(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
// 3️⃣ [DFS 구현]
const DFS = (graph, startNode) => {
const visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...graph[node], ...needVisit];
}
}
return visited;
};
console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]참고
복습 목적 블로그 입니다.