DFS와 BFS 상태 추적 기준

시작 정점 선택

방문 배열을 초기화하고 시작 정점을 자료구조에 넣는다.

start

DFS는 마지막에 넣은 정점, BFS는 먼저 넣은 정점을 꺼낸다.

stack vs queue

인접 리스트나 행렬에서 아직 방문하지 않은 정점을 찾는다.

adjacency

꺼낸 순서와 새로 넣은 후보를 분리해 표에 기록한다.

trace

Stack

최근 후보 우선 한 경로를 끝까지 따라가며 백트래킹 구조와 잘 맞는다.

DFS

Queue

오래된 후보 우선 간선 수 기준 최단 거리를 층 단위로 확장한다.

BFS

Visited

정점 상태 저장 순환 그래프에서 같은 정점을 계속 넣지 않도록 막는다.

공통 필수

경로 탐색 모든 경우를 깊게 시도할 때 DFS가 자연스럽다.

최단 거리 가중치 없는 그래프의 최소 간선 수는 BFS로 구한다.

표현 방식 인접 행렬은 빠른 존재 확인, 인접 리스트는 적은 간선에서 효율적이다.