BFS, DFS 알고리즘

그래프 순회 문제

그래프의 특정 정점에서 다른 모든 정점을 방문하는 문제를 그래프 순회 문제라고 합니다.

flowchart LR
1((1)) 
2((2))
3((3))
4((4))
5((5))
6((6))

classDef visited fill:#FFFFFF, color:#000000
classDef willvisit fill#F5F5F5
classDef notvisit fill:#000000, color:#FFFFFF

	1 --- 2
	1 --- 3
	2 --- 3
	3 --- 4
	2 --- 4
	3 --- 5
	4 --- 5
	3 --- 6
	5 --- 6

모든 상황은 위 그래프에서 1번에서 시작해 6번에서 종료된다고 가정하겠습니다.

BFS

너비 우선 탐색(BFS^{breadth-first search})은 시작 정점으로 부터 인접한 정점을 차례로 방문하며 반복적으로 탐색합니다.

BFS 탐색