Search

그래프 순회 (DFS & BFS)

생성일
2024/09/23
[15강] 그래프(Graph) 순회 (DFS & BFS)
안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph) 순회 (DFS & BFS)에 대해 알아보겠습니다. 목차 그래프 순회란? 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (BFS) 정리 지난 글에서 그래프를 코드로 표현하는 법에 대해서 알아보았습니다. 이번 글에서는 어떻게 그래프를 순회(탐색)할 수 있는지 알아보겠습니다. 지난 글에서 말했듯이 그래프 탐색에 있어서는 인접 리스트 방식을 이용할 예정임 그래프 순회란? 그래프 순회(탐색)란 그래프 내의 모든 노드를 한 번씩 살펴보는 것을 의미한다. 선형 자료구조에서 탐색 선형 자료구조란 순서가 있는 자료구조를 의미한다. 즉, 배열 같은 경우는 원소들이 인덱스 순으로 구성되어 있으니 선형 자료구조라고 할 수 있다. 이러한 선형 자료구조에서의 탐색은 ..
https://gliver.tistory.com/36

그래프 순회란?

•
그래프 순회(탐색)란 그래프 내의 모든 노드를 한 번씩 방문하는(살펴보는) 것이다.
•
비선형 자료구조인 그래프의 순회(탐색)은 시작 노드를 설정해 주어야 한다.
•
그래프 탐색 알고리즘
◦
깊이 우선 탐색 (DFS, Depth-Frist Search)
▪
현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식
◦
너비 우선 탐색 (BFS, Breadth-First Search)
▪
시작 노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식

깊이 우선 탐색 (DFS)

•
현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식
•
시간 복잡도: O(N+M)O(N + M)
◦
NN: 노드의 개수
◦
MM: 간선의 개수
동작 방식
예제 코드 (재귀 함수를 이용한 구현)

너비 우선 탐색 (BFS)

•
시작 노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식
•
시간 복잡도: O(N+M)O(N+M)
◦
NN: 노드의 개수
◦
MM: 간선의 개수
동작 방식
예제 코드 (재귀 함수를 이용한 구현)
원리 설명

내용 정리

•
그래프 순회 알고리즘으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다.
•
두 알고리즘 모두, 노드와 간선을 한 번씩 처리하기 때문에 시간 복잡도는 O(N+M)O(N + M)이다.
•
깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)
◦
일반적인 그래프 순회(탐색)를 구현해야 할 때
▪
DFS와 BFS 모두 사용 가능
◦
시작 노드로부터 가까운 노드 순으로 방문해야 할 때
▪
DFS 불가능 / BFS 가능
•
그러나, 깊이 우선 탐색(DFS)를 공부해야 하는 이유
◦
그래프 탐색 응용 문제에서 DFS를 기반으로 코드를 작성해야 하는 경우가 종종 있음.