[자료구조] DFS & BFS

기본 개념

• 너비 우선탐색 (BFS) 와 깊이 우선탐색 (DFS)는 모두 그래프를 탐색하는 방법
• 정점 (node) 과 정점을 연결하는 간선 (Edge)으로 이루어진 자료구조를 의미함
• 하나의 정점으로부터 마지막 정점까지 모두 방문한다는 것이 특징

이미지 간단순서 정리

• 검정 테두리 원은 정점 (node), 검정 연결 선은 간선 (Edge), 숫자 (빨강, 파랑)은 방문 순서
• DFS는 루트 정점 (가장 첫 순서) 기준 왼쪽 분기를 우선적으로 모두 방문, 이후 다른 분기를 방문함.
• BFS는 방문한 정점과 인접한 정점부터 방문함.

DFS

• 이미지 상으로 왼쪽 그래프
• 루트 정점 기준으로 한 분기를 모두 방문하고, 다른 분기를 방문하여 끝까지 방문함.
• 모든 정점들을 방문하려하는 경우 이 방법을 선택
• DFS가 BFS보다 좀 더 간단함
• 진행 속도 자체는 BFS에 비해 느림

BFS

• 이미지 상으로 오른쪽 그래프
• 루트 정점 기준으로 가까운 정점들을 우선적으로 방문
• 정점을 잇는 노드 간 최단 거리를 찾으려는 경우 사용함.

구현 방식

• DFS : 스택 (Stack) 이나 재귀함수으로 구현
• BFS : 큐 (Queue) 로 구현