DFS 방문 순서
깊게
A
B
D
E
C
F
graph traversal
DFS는 깊이, BFS는 거리 순서가 먼저 드러난다
같은 그래프라도 꺼내는 자료구조가 다르면 방문 순서가 달라진다. 스택은 최근 정점을, 큐는 오래 기다린 정점을 먼저 처리한다.
DFS: stack / recursion
BFS: queue / level
visited: 중복 방지
공통 그래프
BFS 방문 순서
가깝게
A
B
C
D
E
F
자료구조 상태를 보면 두 탐색이 구분된다
DFS stack
초기
A
A 처리
CB
B 처리
CED
결과
A-B-D-E-C-F
BFS queue
초기
A
A 처리
BC
B 처리
CDE
결과
A-B-C-D-E-F