깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)
지난 포스팅에서 그래프의 기본 개념과 용어, 그리고 다양한 표현 방법에 대해 알아보았다. 이번에는 그래프 탐색 알고리즘인 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)에 대해 자세히 알아보도록 하겠다.
1. Connected Components와 Spanning Tree
Connected Components
그래프에서 연결된 vertices의 최대 부분 그래프를 연결 요소(Connected Component)라 한다. 다시 말해, 연결 요소 내의 모든 vertex 쌍에는 경로가 존재하며, 다른 연결 요소에 속하는 vertex로 이동할 수 없다.
Spanning Tree
신장 트리(Spanning Tree)는 연결된 undirected graph의 모든 vertices를 포함하는 트리다. 즉, 그래프의 모든 vertex를 연결하면서 cycle을 형성하지 않는 subgraph다. 신장 트리는 여러 개 존재할 수 있으며, 최소 신장 트리(Minimum Spanning Tree)는 edges의 가중치 합이 최소인 신장 트리를 의미한다.
2. 깊이 우선 탐색 (Depth-First Search, DFS)
깊이 우선 탐색은 그래프의 한 vertex에서 시작하여 최대한 깊이 탐색하고, 더 이상 갈 수 없을 때 이전 vertex로 돌아가 다른 경로를 탐색하는 방식이다.
DFS의 특징
- 모든 vertex와 edge 방문: DFS는 시작 vertex와 연결된 모든 vertex 및 edge를 방문한다.
- 연결 요소의 Spanning Tree 형성: DFS를 통해 방문한 vertices 및 edges은 연결 요소의 spanning tree를 형성한다.
- 시간 복잡도: DFS의 시간 복잡도는 O(V + E)다. (V는 정점의 수, E는 간선의 수)
DFS 알고리즘
DFS(G, v):
v를 방문했다고 표시
v에 인접한 모든 정점 w에 대해
만약 w가 아직 방문되지 않았다면
DFS(G, w) 호출
 |
| DFS 예시 |
3. 너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 그래프의 한 vertex에서 시작하여 인접한 vertex들을 먼저 모두 방문하고, 그 다음 레벨의 인접한 vertex들을 방문하는 방식이다. 마치 잔잔한 호수에 돌을 던졌을 때 물결이 퍼져나가는 모습과 같다.
BFS의 특징
- 모든 vertex와 edge 방문: BFS는 시작 vertex와 연결된 모든 vertex 및 edge을 방문한다.
- 연결 요소의 Spanning Tree 형성: BFS를 통해 방문한 vertices 및 edges은 연결 요소의 spanning tree를 형성한다.
- 최단 경로 탐색: BFS는 시작 vertex에서 다른 vertex까지의 최단 경로(간선의 수가 가장 적은 경로)를 찾을 수 있다.
- 시간 복잡도: BFS의 시간 복잡도는 O(V + E)이다. (V는 정점의 수, E는 간선의 수)
BFS 알고리즘
BFS(G, s):
큐 Q 생성
s를 Q에 삽입하고 방문했다고 표시
while Q가 비어있지 않은 동안:
v = Q에서 삭제
v에 인접한 모든 정점 w에 대해
만약 w가 아직 방문되지 않았다면
w를 Q에 삽입하고 방문했다고 표시
 |
| BFS 예시 |
마무리하며
이번 포스팅에서는 그래프 탐색 알고리즘인 DFS와 BFS에 대해 알아보았다. DFS와 BFS는 그래프를 탐색하고 분석하는 데 중요한 도구이며, 미로 찾기와 최단 경로 찾기 등 다양한 응용 분야에서 활용된다. 다음 포스팅에서는 그래프 알고리즘의 세계를 더 깊이 탐험해 보겠다.
추천글:
(https://hyeonb.blogspot.com/2024/03/blog-post.html)
[자료구조] Graph
(https://hyeonb.blogspot.com/2024/06/graph.html)
