인접 행렬
구현 시, O(V^2)
인접 리스트
구현 시, O(V + E)
재귀함수
or 스택
으로 구현① 장점
큐
에 탐색할 노드들을 저장하는 BFS
에 비해, 메모리 소비가 적음② 단점
큐
로 구현최단 경로
(최적 해
)를 탐색하는 경우 사용① 장점
② 단점
큐
에 탐색할 노드들을 저장하므로, 노드의 수가 많을 수록 메모리 소비가 큼Question) "DFS와 BFS에 대해 설명 해주세요."
DFS
와BFS
는 그래프 탐색 알고리즘 입니다.
DFS
는재귀함수
또는스택
으로 구현하며, 가능한 최대 깊이까지 탐색하는 방식 입니다.
장점은큐
에 탐색할 노드들을 저장하는BFS
에 비해, 메모리 소비가 작습니다.
단점은 최적 해의 탐색을 보장하지 못하고,
Worst Case의 경우, 가능한 모든 경로를 탐색 합니다.
BFS
는큐
로 구현하며, 현재 노드와 가까운 노드부터 탐색하는 방식 입니다.
장점은 최적 해의 탐색이 보장 됩니다.
단점은 노드의 수가 많을 수록 탐색 해야하는 노드가 많아집니다.
또한큐
에 탐색할 노드들을 저장하므로, 노드의 수가 많을 수록 메모리 소비가 큽니다.