[Graph] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

---

1. 깊이 우선 탐색(DFS)

2. 너비 우선 탐색(BFS)

3. 최적 경로와 최단 경로 차이

---

1. 깊이 우선 탐색(DFS)

한 방향으로 끝까지 탐색한 후, 되돌아가면서 다른 경로를 탐색하며 최적 경로를 찾는 알고리즘입니다.

최적 경로는 여러 조건을 고려하여 가장 적합한 경로를 찾는 것입니다.

서울에서 부산까지의 거리만 짧은 것이 아닌 교통 체증, 고속도로 톨게이트 비용 등을 고려하여 길을 찾을 때 사용됩니다.

 

다익스트라, 벨만-포드, 플로이드-워셜 알고리즘에서 사용됩니다.

 

- 동작 과정

1. 시작 노드를 방문하고 스택에 넣음 (또는 재귀 호출)

2. 현재 노드에서 갈 수 있는 노드를 방문

3. 더 이상 방문할 노드가 없으면 이전 노드로 되돌아감

4. 모든 노드를 반복할 때까지 반복

 

2. 너비 우선 탐색(BFS)

시작 노드에서 가까운 노드를 먼저 탐색하며 최단 경로를 찾는 알고리즘입니다.

최단 경로는 단순히 가장 짧은 거리를 찾는 것입니다.

서울에서 부산까지의 가장 빠른 길을 찾을 때 사용됩니다.

 

다익스트라(시간, 비용 가중치 반영) 알고리즘에서 사용됩니다.

 

- 동작 과정

1. 시작 노드를 큐에 추가하고 방문 표시

2. 큐에서 노드를 꺼내 해당 노드의 이웃 노드를 모두 방문

3. 방문한 이웃 노드를 다시 큐에 추가

4. 큐가 빌 때까지 반복

 

3. 최적 경로와 최단 경로 차이

최적 경로는 모든 정점을 연결하는 최소 신장 트리를 구하는 문제고, 최단 경로는 두 정점을 이어주는 최단 경로를 구하는 문제입니다.

서울에서 부산까지 가는 최단 경로, 서울에서 부산까지 가는 데에 걸리는 비용이 최소인 최적 경로입니다.

학부 때 알고리즘을 공부하면서 가장 헷갈렸던 점이 이 내용이었는데 위와 같이 생각하면 이해하는데 도움이 되실 겁니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3